Comments 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.
На пальцах. Пусть мой 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 должен сказать что более близких нет?
> Например, у меня в списке пир 8022, я его спрашиваю — кого ты знаешь максимально близкого к 871e? Он отвечает — это пир 87a0. Я отправляю пиру 87a0 инфмацию что у меня, у ab12, есть документ 871e.
а как определяется что пора прекратить искать ближайший к 871e и уже передать информацию о документе?
Пир 87a0 должен сказать что более близких нет?
87a0 может отдать 2 списка:
1) список известных ему пиров, наиболее близких к искомому ID
2) список известных пиров-владельцов файла с искомым хешем (посколько он хранит файлы, наиболее близкие к его ID, у него и имеет смысл спрашивать владельцев этих файлов)
Причём, 87a0 знает, что владелец файла — ab12, но не хранит его IP, т.к. факт владения — долгосрочная информация, а текущий IP — краткосрочная. Пира ab12 нужно искать по его соседям, у них наиболее достоверная инфа по IP, т.к. они друг друга периодически пингуют.
Клиент, осуществляющий поиск, сам решает, остановить поиск, или двигаться дальше в направлении к искомому хешу.
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.
Хеш или свой идентификатор вы сами себе выбираете случайно ну или не случайно. Скачать можно список узлов — это просто список структур типа ip адрес + udp порт + хеш.
Подобный список можно получить зная адрес и порт подключенного к сети узла.
Собственно как ниже и расписали процесс поиска это по сути два параллельных процесса — ищем новые узлы которые ближе искомому хешу опрашивая уже известные узлы и добавляя их ответы в список опроса и выполняем запрос ресурса на узлах которые достаточно близко к искомому хешу(tolerance zone).
Если узел знает о ресурсе который мы ищем — он выдаст в ответ список источников если ищем файл и список файлов с их именами и хешами если ищем ключевое слово. Вероятность того что узел знает о ключевом слове или файле тем выше чем ближе его собственный хеш к хешу файла или ключевого слова — потому что публикация это тоже самое что и поиск.
Расстояние важно для первой части процесса поиска или публикации — именно оно дает нам возможность двигаться в правильном направлении выбирая нужные ноды и отсекая лишнее.
Например всем кто в опросном списке рассылаем Kad2Req, a тем кто еще и достаточно близко к искомому хешу дополнительно Kad2SearchKeysReq.
в торрентах это MD5
В торрентах SHA1.
А кто-нибудь может рассказать об отравлении DHT?
Типа берем намеренно себе хэш, который максимально близок к хэшу некоторого контента, потом под видом того, что мы знаем где контент хранится выдавать неверные хэши тем, кто за контентом к нам придет?
Типа берем намеренно себе хэш, который максимально близок к хэшу некоторого контента, потом под видом того, что мы знаем где контент хранится выдавать неверные хэши тем, кто за контентом к нам придет?
На каждой итерации поиска запрос рассылается N нодам, максимально близким к хешу.
Для StrongDC++ значение N=50.
Как минимум, надо держать 50 фальшивых нод, но клиенты случайно могут выйти на нефальшивые, достаточно близкие к искомому хешу, но не совсем близкие к искомому хешу.
Конечно, на одном IP можно держать хоть 10000 нод на разных портах, если написать соответствующий софт.
Однако, это заблочит только один хеш. Мой опыт файлообмена говорит о том, что у крупных релизов бывает по 10-15 альтернатив для фильмов с разными хешами (разные рипы, разные вложены файлы), 3-8 альтернатив для игр. Так что, если один хеш плохо качается, в сети появится другой.
Для StrongDC++ значение N=50.
Как минимум, надо держать 50 фальшивых нод, но клиенты случайно могут выйти на нефальшивые, достаточно близкие к искомому хешу, но не совсем близкие к искомому хешу.
Конечно, на одном IP можно держать хоть 10000 нод на разных портах, если написать соответствующий софт.
Однако, это заблочит только один хеш. Мой опыт файлообмена говорит о том, что у крупных релизов бывает по 10-15 альтернатив для фильмов с разными хешами (разные рипы, разные вложены файлы), 3-8 альтернатив для игр. Так что, если один хеш плохо качается, в сети появится другой.
На одном IP не получится держать много нод, ну как минимум без ухищрений. Была идея поднять в облаке супер ноду как-раз с кучей кад клиентов каждый на своем порту — но облом, узел идентифицируется по IP — если порт не совпадает то узел апдейтится, а не добавляется. Конечно можно хеши выбрать сильно разные и теоретически пересечения не произойдет.
Интересно, я изучал DHT в DC++, там тоже заявлен алгоритм Kademlia. Но есть небольшие различия вроде вышеупомянутого (в dc клиент определяется по ip/port), а также там превосходно реализована защита от фильтрации протокола DPI-системами (все пакеты шифруются).
Но зато там нет поиска по словам, только по хешам файлов.
Но зато там нет поиска по словам, только по хешам файлов.
По ссылке «Хороший реверс Кадемлии» pdf в котором в конце рассматривается вариант отравления сети KAD.
Sign up to leave a comment.
Kademlia (DHT) — практическое руководство