#dev (ilita) | Обсуждение разработки I2Pd | i2pd development discussion | http://i2pd.website/

orignal Vort вроде починил ту проблему

Vort теперь сыпятся SSU2: Couldn't update RouterInfo from SessionConfirmed in netdb

orignal счас посмотрим

orignal часто?

Vort 9 штук после рестарта

orignal ну это нормально

Vort ок

orignal у тебя патч стоит,

Vort да

orignal ну так как раз из-за него

orignal ложноположительное срабатывание

weko [21:54:32] <Vort> по поводу лимитов чуть перефразирую - они должны в первую очередь зафиксировать нынешнее положение дел. то есть, при условии нормального исполозования сети, ничего не должно поменяться

weko Ну вот ты знаешь что такое бинарное дерево? Вот в нём нужно хранить флудфилы

weko По моему мнению проблем быть не должно

weko Примерно понял что за k-buckets, похоже просто другой алгоритм

weko_ orignal: короче k-bucket это для поиска среди всех нод

weko_ Что уже сделано по факту

weko_ Не очень я понял зачем так усложнять и зачем под это термин

weko_ Насчёт алгоритма там - такой же как я и продумал

weko_ Только я его расширил чтобы несколько ближайших возвращать

weko_ Ну в голове)

Vort не давала мне покоя атака 6го числа, решил посмотреть подробнее на сохранённые мной RI

Vort и выяснил одну особенность: в фейковых RI были IP:порты реальных флудфилов

Vort скорее всего, orignal в курсе, но на всякий случай решил написать

weko_ Интересно

weko_ Но мало что меняет

weko_ Проверить всё так же можно

weko_ Просто по ключу который у флудфила и тот что в RI

weko_ Да кстати!

weko_ У нас же не может быть на одном адресе и порту два роутера

weko_ Так и определять тоже можно

whothefuckami О, вы профилирование флудфилов пилите?

weko_ Не это другое

weko_ Хотя про это речь была выше

weko_ Полотна там)

whothefuckami И как оно будет работать:

whothefuckami ?

whothefuckami Тебя наверно выкинуло, когда я это спрашивал

whothefuckami <whothefuckami> И как оно будет работать:

whothefuckami <whothefuckami> ?

tetrimer Всем доброго! У меня под дебианом 11 последняя сборка с гитхаба получилась размером в 90Мб - это нормально?

Vort tetrimer: с отладочной информацией наверно

tetrimer Специально - ничего не включал...

Vort так её специально выключать надо

Vort ну или не обращать внимание

Vort 100 мегов так 100 мегов

orignal Vort в смысле реальных?

orignal make DEBUG=N надо если 90 мег смущает

weko [11:31:23] <whothefuckami> Тебя наверно выкинуло, когда я это спрашивал

weko Я выходил. Будет когда будет сделано как минимум

orignal что с атаками сегодня?

weko Ничего кроме туннелей я не видел

weko Надо джавистам сказать чтобы снизили параметры для бана роутера

orignal кончился бюджет или готовят новый вариает?

weko Потому что к меня TCSR меньше когда больше транзитных туннелец

weko туннелей*

weko Фиг знает

weko Скорее второе

orignal они очевидно следят за нашими коммитами

weko Походу да

weko stats.i2p/cgi-bin/total_routers_day.cgi

weko Пошло вниз с 3 тыщ

weko Пару дней было 3 тыщи

weko А тут вниз пошло

orignal сразу после того коммита атаки с вложенным чесноком прекратились

weko А мы уверены в этом?

weko Есть у кого без коммита фф?

weko [12:31:05] <orignal> сразу после того коммита атаки с вложенным чесноком прекратились

weko Кстати это интересно. Возможно атакующий не сильно хочет навредить. Иначе бы продолжал. Или он боится что мы его вычислим (что возможно)

weko Хотя будь я атакующем, я бы просто накупил бы анонимных впсок

orignal если он кидал напрямую то да

orignal то что атаки шли только через NTCP2 такое возможно

weko Ну короче я могу алгоритм рассказать для dht

orignal да я уже тоже разобрался

orignal напишу на днях

orignal код

weko А я тогда зачем нужен был?)

weko ))

orignal ну давай рассказывай

weko Хорошо

orignal я только начал

orignal что такое k-bucket в нашем случае

orignal в терминах роутреов

weko У нас всё что связано с k-bucket уже сделано

weko Как я понял

weko Там алгоритм простой, я не пойму зачем усложенено этим термином

orignal у нас вообще ничего нет

orignal ты расскажи как делается поиск ближайшего быстро а не перебором

weko Ну вот

weko Я как раз собирался

weko Просто ты спросил я сказал))

orignal давай тогда про поиск

orignal с метрикой xor

orignal я только мелком глянул что там некое дерево строится

weko Флудфилы лежат в бинарном дереве, первый бит - две ветки из корня, второй бит - ветки из предыдущих веток и так далее. Если есть ветка, и дальше до флудфила нету ветвлений, то мы все ветки не делаем, а храним сразу после ветвления.

weko Алгоритм: берём ключ, первый бит - если 0, идём на ветку 0, если 1 - идём на ветку 1. 2 бит также: 0 на ветку 0, 1 на ветку 1. Если нужной ветки нету, идём на оставшуюся ветку. Таким образом идём до флудфила. Этот будет первым ближайшим. Дальше идём вверх до ветвления (в

weko нашем случае всегда на один вверх), и повторяем тот же алгоритм (на ветвлении обратно не идём), получаем второй ближайший. Третий точно также.

weko С не флудфилами тоже самое

orignal так погоди

orignal биты это просто его хэша?

weko Да

weko Биты ключа по которому ищем

orignal хорошо

orignal а как это помогает с xor?

weko SHA256(key + ddMMmyy)

weko Там xor как раз позволяет так сделать

weko Короче если мы идём на такой же бит, то мы в итоге 0 получаем

orignal нам же надо упорядоичвать не сами хэшт

orignal а xor с ними

orignal я не понимаю как это помогает

weko Нарисуй дерево, таблицу xor и поймёшь суть

orignal понимаешь мы сравниваем не адрес с тем что в дереве а хэши

weko Когда мы идём на тот же бит, мы гарантируем что в результате xor будет 0 ( 1 1 - 0, 0 0 - 0 по таблице)

orignal счас погоди

orignal объясни мне где в этом алгоримтме xor?

weko Нигде)

weko В этом и суть

orignal так не будет же работать

weko Будет

weko Нарисуй дерево

orignal нам надо найти ближайшие по xor

weko Бинарное

weko Дааап

weko Смотри

orignal а не ближайшие по самому значения

Vort "<~orignal> Vort в смысле реальных?" атакующий (6го числа) взял базу реальных флудфилов и наделал клонов RI с небольшими изменениями

weko Мы в приоритете хотим чтобы ведущие были нули

orignal то что ты описал это обычный бинарный поиск

weko Неееь

weko Нет)

orignal Vort понял

weko [12:49:22] <weko> Мы в приоритете хотим чтобы ведущие были нули

weko Мы начинаем с ведущих битов, начнём с первого:

weko Чтобы в xor было 0, надо чтобы бит был такой же, как и в ключе. Соответственно мы идём по ветке с таким же битом

weko Тоесть две единицы дадут 0

weko И два нуля дадут 0

weko В приоритете мы заполняем нулями ведущие биты, соответственно мы с них начинаем

orignal ведущие нули это и есть xor

weko Потом если где то нету выбора, идём куда позволяет дерево

orignal я правильно тебя понимаю что мы можем написать std::map со скоми копаратором?

orignal чтобы не городить велоспиды?

weko Сейчас подумаю

orignal просмотрим описани std::map или std::set

weko Компоратор что это?

orignal фнунция которыая сравнивем 2 элемента и говорит какой из них меньше

orignal испольщуеися у нас например в TunnelPoll.h

orignal чтобы упорядочивать тоннели по времени

weko Не получится

weko Нужно именно дерево

weko Суть алгоритма такая

weko Я придумал сначала , потом почитал , у меня сошлось

weko С тем что написано

weko Вот тут:

weko codethechange.stanford.edu/guides/guide_kademlia.html

orignal там там внутри дерево

weko Суть дерева, что ты можешь ходить как вниз, так и вверх

weko Сейчас подумаю можно ли хэш таблицой сдедать

orignal ну вот я и спрашиваю нельзя ли как то присбоачить готовые струутры

orignal там в этом std::map много чего можно задачть

weko Тогда смотри

orignal иными словами меня интересует практическая сторона

weko Ключ тогда любое число, а в значении будет ключ родителя и ключи двух ветвей

weko Тогда можно будет и вверх и вниз

orignal посмотрю как сделать

orignal без велосипедов

weko Я могу пример кинуть

weko Как делать бинарное дерево

orignal мне бы с std::map

orignal или может в бусте что ниюудь есть

weko Окей

weko Насчёт map я не уверен что можно по-другому

orignal как то надо бы восипользоваться готовыми стурктурами или частично алгоритмами

weko Ну врядли есть dht в стандартных либах

weko Бинарное дерево может есть

orignal не само dht а стуктуры для хранения дерева

orignal на основе которых делать dht

weko Это я про алгоритмы

orignal не писать же мне самому struct Node ( Node * left, *right; RouterInfo * flodfill; }

weko Ну если есть то не стоит

orignal вот я и пытаюсь найти готовые

weko Почему map менее оптимально: хэш таблица это массив, тоесть когда будем увеличивать, то массив иногда придётся пересоздавать. С деревом такое не нужно

weko В случае i2p это не сильно критично

orignal map это дерево

weko Но это я чисто теоретически говорю

orignal внутри

weko А, да?

orignal да

orignal там именно вот такое дерево как ты говоришь

orignal и бинарный поиск по дереву

weko ну там не со совсем поиск

weko Точнее он не строгий

orignal в map тоже можно не строгий

weko Если у нас нету нужной ветви мы не вываливаем ошибку, а идёи дальше

weko А несколько можно искать?

orignal а например найти "ближайший меньгийЭ

orignal и сдвинуться дальше итератором

weko А, да, ответ на вопрос где xor - xor там где мы выбираем ветку

weko А выбираем мы её так, чтобы в xor был 0 в приоритете, что обеспечивает меньшее число

orignal ну вот можно ли наеисать компаратор таким образом

weko Не знаю

orignal вот это по уму и надо продумать

orignal я попробую ))

weko Компоратор он что может сравнивать? Две ветви?

orignal может там можно переопделить алгоритм

orignal два ключа

weko Тогда я думаю нельзя

weko Ну я иак думаю

weko Ты лучше знаешь

orignal ну тогда попробую написать велосипед

orignal для началап

weko Понял суть , как нужно ходить по дереву?

orignal да

orignal я понял что это бинарное дерево но с хитрой разбирвкой на левую и правую ветку

weko Да

weko Левая например 0, правая 1

weko На концах соответственно флудфилы, которые этим веткам соответствиют

weko Тоесть если у флудфила первый бит 0, то он будет относительно корня на левой ветке и так далее

weko Думаю понятно

orignal угу

orignal займусь

orignal ибо пора

whothefuckami Хмм, а неплохо джависты придумали

orignal что именно?

whothefuckami Ну дерево

orignal а они причем тут?

whothefuckami С битами хеша

orignal kademlia была в ишаке

whothefuckami Они не придумали???

orignal когда i2p даже еще а проекте не было

orignal это алгорим kad

orignal я потому и предлагал код ишака поспомотерть

weko Kademlia это вообще отдельная штука, да)

weko В i2p просто наработки используются

weko Там даже протокол есть свой

orignal kademlia это и есть DHT с xor

orignal i2p оттуда взяли dht

orignal осталось решить что будет делать велосипед я или polistern ))

orignal ибо у нее та же самая проблема

polistern Которая из проблем?)) orignal, не смотрела iMule, всё откладывала на потом нормальный DHT.

orignal polistern реализация дерева для DHT

orignal как говорит weko

orignal это просто бинарное дерево

orignal у которого выбор ветви осуществляет не сранением элементов

orignal а по битам ключа

orignal вопрос тут в том чтобы мы не начали делать одно и то же

weko При чём чтобы несколько выбрать, нужно подняться вверх и таким же способом найти ещё один

weko Ну и так сколько нужно раз

polistern Я не скоро за код сяду и тем более dht не в приоритете. Так что не переживай)

weko Соответственно на ветви где уже были ходить не надо

orignal ладно понял тогда у меня потом скопируешь когда сделаю

polistern В Java bote есть реализация Kademlia ванильного, если что

orignal нам то нужна плюсовая

polistern Ну да, но я про алгоритмы, просто если кому интересно)

polistern K-bucket'ы эти, распределение, разделение

orignal так weko правильо говорит что можно и без них

weko K-bucket по сути просто термин

weko А по факту это то уже сделано

weko Ищем ближайший пир в базе

weko Спрашиваем у него ближайший пир

weko Ну и так далее

weko В i2p ещё и публикация по dht

weko А в торрентах вроде такого нету

polistern А конкретно о чём вы? Что для сета и мапы дописывать собираетесь? Более хитрые компараторы?

zzz orignal, FYI, I'm increasing the minimum router version for floodfill and tunnels from 0.9.38 to 0.9.51

whothefuckami Я так понял, они хотят переписать поиск по мапе

whothefuckami Мы же ищем не точное совпадение

whothefuckami А ближайший по хешу флудфил вроде

whothefuckami idk

whothefuckami Можно унаследоваться от мапы, чтобы получить её внутренности с кишками

whothefuckami И пилить свой метод find

whothefuckami Но я так глянул в код мапы

whothefuckami Пиздец нахуй, лучше туда не лезть

whothefuckami Зато теперь знаю, что там внутри красно чёрное дерево

orignal zzz thanks. will do the same

zzz ok. 0.9.51 is short TBM

orignal polistern кнкретно о флудфилах

orignal где надо искать ближайшие все время

orignal const int NETDB_MIN_HIGHBANDWIDTH_VERSION = MAKE_VERSION_NUMBER(0, 9, 36); // 0.9.36

orignal should I also change it?

weko why such a drastic change?

weko the*

orignal потому что

orignal <zzz> ok. 0.9.51 is short TBM

weko Что такое TBM

weko Ааа

weko Пон

weko Тогда ладно

orignal tunnel build message

weko Я понял, да))

weko Я думал логично делать всегда на 10 версий назад например

weko Каждый раз на единичку менять

orignal это давно обсуждалось кстати

weko Ну я не спорю

weko Что это нужно

zzz there's very very very few routers 0.9.30 - 0.9.50

weko Yes I see

weko 0.9.29 - look like some organization verify code, and don't want verify code adain

weko Or repository

zzz Vuze

weko Привет солярка

weko Где атака солярка

weko Ты же обещал

orignal вроде нет

orignal он вчера сосскочил с темы

weko Он говорил готовит вроде

orignal видать бюджет кончился

Словесник-Былинник vtornik ya dovoril tebe

Словесник-Былинник budet vo vtornik

weko Мамка шнур от компа забрала

orignal а почему во вторник?

Словесник-Былинник я говорил тебе 2 дня назад. Он сказал мне в личке.

Словесник-Былинник но под другим ником ... но он похоже

Словесник-Былинник те же обороты речи

Словесник-Былинник вчера про патч спрашивал

orignal ха ха

orignal предсказуемо

Словесник-Былинник я честно ответил, как и всегда... я сбилдал все что на гите и все. патчей не ставил

orignal а разве это не правда? ))

orignal нет никаого патча же

Словесник-Былинник ты же знаешь, что я всегда правду говорю... просто не все способны ее услышать :)))

Словесник-Былинник у многих тут мнение, что если нет заговора .. то это подозрительно. Ну психи, что говорить то ?

Словесник-Былинник опять же, это мое подозрение что это был он или один из них. Гарантий нет.

whothefuckami <weko> Мамка шнур от компа забрала

whothefuckami кде банальное уважение к врагам?

whothefuckami тьфу

weko Дак он тролль

weko Уже давно выяснили

orignal whothefuckami разве он враг?

whothefuckami orignal: ни знаю

orignal тролль причем хамовалтый

whothefuckami хамовалтый - это украинское слово?

whothefuckami ru.wiktionary.org/wiki/%D1%85%D0%B0%D0%BC%D0%BE%D0%B2%D0%B0%D1%82%D1%8B%D0%B9

orignal хамоватый

orignal опечатка просто

qend <~orignal> не само dht а стуктуры для хранения дерева

qend подойдет boost::multi_index_container?

orignal не знаю

orignal не смотрел еще

orignal weko так как же мы ищем ближайшие без K-Bucket-ов?

weko k-bucket это же другое

weko В любом случае

orignal вот дошел я по дереву до послденей развилки где ветки соотвествующей биту нет

orignal дальше что?

weko Дальше идём по другому

orignal то есть у меня занчение бита 0 а там только ветка для 1

orignal след шаг какой,

weko Значит идём по 1

weko Если выбора нету

orignal идем вниз или обртано вврех?

weko Если нет выбора идем дальше по тому, что есть

weko Внмз

weko Вниз

orignal пошли по 1

orignal дальше там все ветки есть

orignal и куда?

weko Ну доходим до флудфила

orignal я вот это не понимаю

orignal до какого? там их могут быть тысчи

weko Хорошо сейчас напишу по-другому

orignal я не понимаю как мы выбираем ближайший

weko Да но мы то к одному придёи

weko Хорошо щас

orignal давай распиши поиск пошалгово

orignal как сранивать биты и выбирать ветку мне понятно

weko Окей, давай объясню почему это обеспечивает наименьшее число

weko Сначала мы обеспечиваем как можно больше нулей в ведущих битах, до первой единицы

orignal минутку у меня собрание

weko Ок

weko Суть проста - чтобы число было наименьшим, нужно идя от старшего бита к младшему как можно чаще делать ноль

weko Вот например мы прошли по левой ветке. Все узлы с правой ветки исключаются, потому что у них в этом разряде единица

weko А слева ноль

weko И какое бы число не было справа, слева точно есть число меньше

weko Точнее все числа слева меньше чем числа справа

weko 000, 001, 010, 011 < 100, 101, 110, 111

weko Мы идём налево

orignal левая у нас 0 а правая 1?

weko ну например

weko Можно сделать наоборот, но так удобнее

weko Мы же не арабы

orignal для определенности разговоря

weko А чтобы гарантировать, что XOR даст 0, нужно идти на тот же бит, что и в ключе (исходя из таблицы XOR)

orignal это понятно

orignal а когда уперлись что нет ветки с тем битом то как дальеш?

weko Идём по другой ветке

weko Расстояние же может быть не нулевым

orignal сравнивая следущие биты что ли?

weko Нет, просто идём по этой ветке

orignal так взяли мы ее

R4SAS велосипедисты

orignal а дальше?

R4SAS )))

orignal там же целое дереров

weko Ну а там точно также считаем

orignal R4SAS мы тебя слушаем

weko Алгоритм не меняется

orignal то есть дальше опять биты сраниванием на след пощициях?

weko Да

weko Точно также

orignal все понял

weko Если есть бит - идём, если нету, то идём по другому

orignal пока не упремлся в лист

weko Да

orignal нашли первый

orignal а второй как?

orignal R4SAS ну так как без велосипеда?

weko Потом идём вверх до развилки (при правильном хранении всегда выше на 1 ветку), и на этой развилке идём в другой бит, дальше по алгоритму

R4SAS orignal: алгоритм шеннона-фано помнишь?

orignal и не знал джае ))

orignal меня интересует парктическая реализация

R4SAS там конечно про сжатие, но все же

orignal weko ага понял

orignal R4SAS надо конкретно счас решить проблему с флудфилами

weko Принцип "ближайший, кроме того что уже выбрали"

orignal weko я попробую написать

orignal как ты говоришь и сравнить резалттаты с тупым перебором ))

weko Понял что такое правильное хранение?

orignal твое объяснение понял

weko Тоесть нам не нужно между флудфилом и ближайшим (вверх) перекрёстком хранить кучу нод дерева, потому что они ничего не решают

weko Если там нету перекрёстков, то по алгоритму что так то сяк попадём в этот роутер

R4SAS codethechange.stanford.edu/guides/guide_kademlia.html#search-tree-partitions-kademlia

R4SAS Key/Computer Lookups тоже посмотрите

weko Я это кидал кстати уже)

weko Я там как раз таки убедился что я правильно придумал

weko Key/Computer Lookups это как ищущему искать

orignal R4SAS так может тогда ты и напишешь код для флудфилов?

R4SAS Blinded message

orignal аналогично

orignal а когда время будет ты готов написать?

R4SAS я думаю weko быстрее напишет)))

orignal он на плюсах не умеет ))

orignal скорее уж я

Vort вы хотите сделать алгоритм, дающий тот же результат, но чтобы быстрее был?

orignal Vort да

orignal не тупо идти по всему списку а искать быстро

Vort в таком случае можно для тестовой (локальной) версии оставить старый + поставить новый рядом. делать два вызова и сравнивать

orignal что я и собираюсь сделать

Vort окей

orignal итак первое что там нужно это операция взятия бита

R4SAS при чем итерируемая

Most2 03.<kerlumic> берешь маску 0х0000нужныйбит00000 и делаешь И

orignal бля

orignal как делать я знаю

orignal на самом деле там сдвиг

orignal просто говорю

orignal R4SAS в смысле итерируемая?

R4SAS ну бит за битом чтобы брать

orignal просто выбор бита номер N

R4SAS либо сдвигать, как ты говоришь

orignal для чего?

orignal бит за битом брать

R4SAS ну, разве это не побитовый итератор получается?)))

orignal я не виже от него выгоды чем просто брать по порядку по номеру

weko Вроде бы любой сдвиг за O(1), так что не суть

orignal там получается 2 сдвига и выбор элемента массива

orignal выигрыш от знания предыдщей позиции не просматривается

weko Процессор умеет двигать на любое число))

orignal угу. ему без разницы

R4SAS процессор ничего не умеет. его надо заставлять это делать)))

weko Ну ему можно команду дать и он сделает - значит умеет))

weko Ему главное сказать, их каких регистров брать число, сдвиг и в какой регистр класть результат))

orignal смотрим как я это сказал процессору в последнем коммите ))

R4SAS и че, каждый раз вызывать собираешься?

R4SAS с подрезанием бита

orignal так это мизер

weko Особенно если сравнить с перебором...)

orignal ладно попробуем потом посмотрим как будет работать

orignal можно будет дальше соптимизировать

weko Я сейчас пока что думаю, потому что кое-что не понял

weko Ладно щас

weko А, я понял, всё)))

orignal я так понимаю тут высота дерева не более 256

orignal соотвествнно и глубина рекурсии

weko Да, но по факту меньше будет

weko Если не хранить лишнего

weko Но да высота не больше 256

R4SAS да там не то что лишнего

R4SAS там просто не будет столько записей

weko Ну если везде хранить по 256 звеньев, памяти не напасёшься

weko Даже на текущие 10-15к роутеров

orignal всегда 256 будет

orignal на каждый бит вевление дерева

R4SAS да, только не на каждой ветке будет продолжение

weko Я писал - нам не надо лишнего хранить

weko +)

orignal как только ты вставишь первый хэш

orignal у тебя сразу будет дерево глубиной 256

orignal на этой ветке

weko В идеале на этом этапе должно быть глубиной в 1 ветвь

weko Ещё раз напишу

R4SAS weko: у тебя сразу оно раскладывается на полное дерево

R4SAS по всем биам

R4SAS битам*

weko Я не спорю что так можно

orignal а при удалении будет обратная рекурсия

R4SAS но я понимаю чего бы хочешь

orignal если удляем последнюю ветвь узла то удаляем и узел

weko R4SAS: чтобы память не кушать

orignal я просто предаюсь размышлениям ))

R4SAS ты хочешь чтобы было 01110110 и 01110000 только до 01110 разворачивать

R4SAS а на концах уже чтобы лежали нужные записи

R4SAS но так не работает

weko Почему ?

orignal а если потом придется втсаавить 01110100 ?

weko Ну добавим нод

R4SAS потому что map фиксированный

weko Это же опять же O(1)

weko Аа

R4SAS как минимум

orignal ну можно наверное да

orignal неее я map не буду делать

weko Мы не полное дерево храним а только то, что нужно для вычисления

weko Таким образом экономим процессорное время и память

weko Вместо 256 итераций будет ну от силы 30

Most2 03.<kerlumic> а можно подробное условие задачи?

weko kermlic алгоритм для DHT - поиск нескольких ближайших флудфилов по заданном ключу

weko Ближайший - значит при побитовом xor ключа и флудфила даёт наименьшее число

Most2 03.<kerlumic> так dht это же двусвязный список, ты туда кладешь ноду и сразу прилинковываешь к ней ближайшие ноды, при этом список отсортирован так что можно ноду по ключ <clipped message>

Most2 03.<kerlumic> у бинарным поиском найти

Most2 03.<kerlumic> и от нее влево и вправо пускаешь курсоры и собираешь ближайшие ноды

Most2 03.<kerlumic> или я чего-то не понимаю?

weko Это другой DHT

weko Вроде

weko Тут Kamelia

orignal согласен так можно сделать да

weko Kademlia*

weko А как ты отсортируешь заранее для каждого ключа?

weko Для бинарного поиска нужна сортировка

weko А для каждого ключа будет разный порядок

Most2 03.<kerlumic> не будет, влево присоединяешь ключи которые меньше вставляемого, вправо - которые больше. Сортировка автоматическая

weko Для каждого ключа разная метрика дальности

weko У тебя пришёл новый ключ, а для него другая сортировка уже

weko Он ближе будет к другим флудфилам

weko И другой порядок их близости

Most2 03.<kerlumic> а, я думал b - a, тогда я не полностью понимаю условие задачи, получается

weko Ты наверное про Chord говоришь

weko Близость измеряется числом XOR(key, floodfill)

weko Флудфилы всегда одинаковые

weko Но вот ключи - нет

weko Они всегда новые приходят

Most2 03.<kerlumic> то есть если один ключ имеет близость 10, а другой 25, это не говорит о расстоянии между ключами?

weko Близость к чему ?

weko У одному флудфилу?

Most2 03.<kerlumic> ну видимо к флудфилу раз XOR(key, floodfill)

weko Близость ключей никто не смотрит

weko Либо ключа и флудфила

weko Либо двух флудфилов ( но в i2p не нужно)

Most2 03.<kerlumic> так, получается есть много флудфилов и есть много ключей, ключи часто меняются а флудфилы нечасто. В чем задача DHT?

Most2 03.<kerlumic> искать ключи ближайшие к конкретному флудфилу? Или флудфилы ближайшие к ключам?

weko DHT более объёмная тема чем просто алгоритм

weko Флудфилы ближайшие к ключам

weko Задача конкретно алгоритма найти N флудфилов, которые будут максимально близкими к данном ключу

weko Максимально близкие значит наименьшое число при побитовом XOR(key, floodfill)

weko Ну соответственно ключи и флудфилы по 256 бит

Most2 03.<kerlumic> алгоритм вычисления расстояния обязательно должен быть через XOR(key, floodfill)?

weko Обязательно

weko Иначе не сделать оптимально

weko Специально XOR используется чтобы можно было сделать

weko можно было сделать O(1)

weko *

Most2 03.<kerlumic> то есть (key - floodfill) тупой математикой уже не будет о1?

Most2 03.<kerlumic> просто проблема в том, что получается нет связи в близости ключа от одного флудфила и в близости ключа от другого флудфила, то есть придется либо каждый ра <clipped message>

Most2 03.<kerlumic> з вычислять полностью, либо хранить по списоку расстояний до ключей на каждый флудфил

Most2 03.<kerlumic> не понимаю как иначе

weko При разности не будет работать DHT

weko kerlumic могу дать подсказку если сам думаешь

Most2 03.<kerlumic> ну ты предложил вот это дерево, которое по сути является комком, возможно немножко более сжатым, из этих самых списков расстояний для каждого фулфилла

Most2 03.<kerlumic> я думаю сам, но я очень болею сейчас, да и вообще я много туплю

weko Мы специальным алгоритмом идём по дереву

weko Почитай как я лосю объяснял

weko [19:34:06] <Most2> .<kerlumic> то есть (key - floodfill) тупой математикой уже не будет о1?

weko С разностью для близости нужно будет как можно меньший ключ и как можно больший флудфил, что по итогу не будет помогать искать нужные флудфилы

weko Я в голове понимаю почему

weko Но объяснить хз как)

weko Короче разность не подойдёт

weko Ты если придумаешь, поймёшь почему xor

Most2 03.<kerlumic> помогать будет дико, потому что расстояние между фулфиллами станет математическим свойством для ключей, которым можно будет пользоваться. Можно будет вз <clipped message>

Most2 03.<kerlumic> ять ключи и флудфилы и забить это всё в один отсортированный двусвязный список. Опять-таки берешь нужный ключ, два курсора от него в разные стороны и ищешь <clipped message>

Most2 03.<kerlumic> ключи которые являются флудфилами

weko Даже не говоря про то что это не работает, у тебя O(n) алгоритм

weko Что слишком много

HidUserZ kerlumic двусвязный список намного медленее чем дерево

weko XOR was chosen because it acts as a distance function between all the node IDs. Specifically:

weko the distance between a node and itself is zero

weko it is symmetric: the "distances" calculated from A to B and from B to A are the same

weko it follows the triangle inequality: given A, B and C are vertices (points) of a triangle, then the distance from A to B is shorter than (or equal to) the sum of both the distance from A to C and the distance from C to B.

Most2 03.<kerlumic> HidUserZ: ты не учитываешь что он отсортированный, а предложенное выше дерево вообще ничего не сортирует, я не понимаю как помогает отделение ключа с нулем в т <clipped message>

Most2 03.<kerlumic> ретьей позиции в левую ветку, а с единицей в правую

HidUserZ kerlumic так это и есть сортировка

HidUserZ на основе адреса ты можешь понять в какую сторону идти

Most2 03.<kerlumic> а зачем мне идти по дереву, если у меня уже есть этот адрес? В дереве хранится что-то кроме адреса?

weko Дерево позволяет не перебирать

HidUserZ kerlumic задача DHT - по хешу найти IP адрес ноды

weko А отсеивать каждый раз половину

HidUserZ для этого нужно пройти все промежуточные узлы и дойти до искомой ноды

Most2 03.<kerlumic> ага, то есть после прохода по дереву со сравнением каждого бита через XOR отдельной математической операцией там все-таки будет лежать ip

Most2 03.<kerlumic> бинарный поиск по индексам отсортированного списка ничем не уступит по производительности бинарному дереву

HidUserZ нет

HidUserZ с чего ты так решил

HidUserZ стоп а что за бинарнй поиск по индексам

HidUserZ ты предлагаешь составить всю карту сети и там искать что-то?

weko Он не понимает что для бинарного поиска придётся сортировать для каждого ключа

weko А это уже n log n

Most2 03.<kerlumic> в том-то и прелесть что не пришлось бы, будь у нас a - b. Ладно, будем думать что я чего-то не понимаю, пойду спать

HidUserZ kerlumic

HidUserZ a - b ты получишь дистанцию

HidUserZ дальше что сней сделаешь?

Most2 03.<kerlumic> задача была в поиске ближайших по дистанции флудфилов к ключу

zzz need any help on DHT/Kad ?

weko Я не знаю как объяснить почему разность не работает

HidUserZ kerlumic ну да, чтобы они сообщили адрес искомого флудфила

HidUserZ zzz: we are trying to explain to a person how DHT works

HidUserZ No, thanks

zzz :)

weko zzz: oh we already invented algorithm

weko And verify it with resources

Most2 03.<kerlumic> they're trying to optimize xor(key, floodfill) by using trees with compression

weko O(m), where m - num of required RIs

orignal zzz we are trying to implement Kad DHT

orignal because floodfills lookup is too slow now

zzz yeah ours is slow too, good luck :)

weko zzz: are you also have just search in order?

orignal ours is not slow it's juts dumb

weko have you also*

Most2 03.<kerlumic> беда в том что разбивая 256-битный ключ на бинарное дерево с битами тебе придется этот XOR делать для каждого бита по отдельности, что будет в 256 раз медленнее <clipped message>

Most2 03.<kerlumic> чем один XOR. Я не понимаю как оно поможет со скоростью... Мне точно пора спать

orignal we go through the list of floodfills and compare

weko kerlumic этот вопрос тоже уже решён

zzz we sort the entire list of floodfills by closest-to-the-key

Most2 03.<kerlumic> уже прям в коде?

zzz so we are dumb too

weko zzz: oh sort is more stupid...)

weko O(log n * n)

weko When our have O(n)

orignal zzz, polistern mentioned you have better structured in I2P-Bote

zzz maybe, I don't know that code

weko kerlumic нет, но понятно что НЕ нужно записывать

zzz we sort because we're looking for about 10 closest, then classify them good/ok/bad, sort those 10 by rating and closeness, then query them in order until we get an answer

weko Hm

weko Rating...

zzz same idea, m-closest

weko Sort don't need there anyway

zzz where for us m ~= 5-10, then pick the best 3 out of those

zzz sure, we could do O(n), good idea

orignal zzz, when I send Datetime in NTCP2 should calculate it same way as in SSU2?

orignal I have discovered I never send it there

zzz you mean the 500 ms thing?

orignal yes

weko Or better O(m), where m - num of required FFs. We implement this now

zzz sure, do it the same

orignal rounding instead truncating

orignal thanks

zzz it's easy to keep a tree closest to yourself (same key) but I don't know how to do a tree that works for closest-to-arbitrary-key searches

weko Yes I explained this to original

weko I can send link

zzz standard DHT is closest-to-yourself

weko Ye?

weko Hmm

orignal zzz, basically binary tree

zzz and in i2p even that changes every day at midnight

orignal where you decide lerft or righ but next bit in hash

orignal it doesn't matter

orignal tree contains floodfill hashes only

orignal that never change

orignal so you only change this tree only when you add/remove a fllodfiil

weko codethechange.stanford.edu/guides/guide_kademlia.html

weko I verified my notion here:

zzz might work

zzz if you do it by hash

zzz the strange thing about i2p dht is you're not the closest router to yourself ((

zzz even a tree isn't O(m), it would be something like O(m log n)

weko Yes but it not matter for us

weko Yes tree will O(m log n)

weko In memory

weko Not a problem I guess

weko We not closest to yourself, but we need calculate it

orignal you will see my implemnetation soon

orignal it pomises to be simple

zzz yes pretty sure you are right, a tree of hashes would work well

weko Check link above, there exploration

weko Explainetion

weko Oh

weko Idk this word

weko Explained there*

zzz this is where my lack of a comp. sci. degree hurts me, I never think of using trees. Real programmers always think of trees

orignal )))

weko Trees... Green...)

zzz how do you find the m closest for m > 1? find the closest and then "back out" of the tree?

weko Yes

weko Back out and go ahead for next FF

weko It is good idea what we should take 10 and sort by rating

zzz we do have a "real kad" implementation also, but we don't use it for finding closest ff ((

weko But maybe better place in tree only good FFs?

weko zzz: why?

zzz been on my todo list for about 15 years

zzz jrandom stuff

weko If you have implementation already...

weko Why you can't use it

zzz I think all routers are in it, not just ff

zzz it's a big mess, thanks jrandom

weko Oh

weko Why you can do same code, but take only FFs?

weko Can't*

zzz the other problem with using kad is the kbuckets overflow. So you don't want to use that. A tree is better

zzz it would be dumb if you had the RI but it wasn't in the kbuckets so you didn't know

zzz kbuckets works well for closest-to-you but terrible for closest-to-arbitrary key

weko We don't use kbuckets

orignal we are not going to use kbickets ))

zzz our "real kad" code is kbuckets. we use it for snark DHT, but mostly unused in netdb

weko Oh

weko Okay

weko Then it is not good for RIs

zzz weko, I recommend you read the paper "Hashing it out in Public"

weko Thank

weko I will read

zzz that's what the java "iterative search" is based on

orignal так я не понял в чем проблема то?

Vort заглянул в логи. по-прежнему изредка вылазят RouterInfo: Can't open file. но помимо этого ещё стал замечать NetDb: DatabaseLookup for zero ident. Ignored. тоже редкие

orignal пока к ацетону присоединиося

Vort ок