Herbivore (протокол)

Вся сеть представляет собой кольцо, созданное из небольших групп из ${\displaystyle \sim k}$ пользователей.

глобальная топология

Глобальная топология сети описывается протоколом входа. Главная его цель — сохранить анонимность участников, путём лишения каждого права выбирать в какую группу вступать. Это делается для того, чтобы злоумышленники не «захватили» всю группу и, таким образом, не раскрыли анонимность участников. Метод состоит в следующем: у каждого пользователи и у каждой группы есть свой уникальный ключ. Для того, чтобы войти в сеть пользователь должен сгенерировать пару ключей ${\displaystyle K_{public}/K_{private}}$ - открытый/закрытый ключ. После этого случайно генерируется вектор ${\displaystyle Y}$, не равный открытому ключу ${\displaystyle K_{public}}$, такой, что младшие ${\displaystyle m}$ бит ${\displaystyle f(K_{public})}$ равны младшим ${\displaystyle m}$ битам ${\displaystyle f(Y)}$, где ${\displaystyle f}$ это необратимая функция. Значение ${\displaystyle g(K_{public},Y)}$, где ${\displaystyle g}$ - необратимая функция, становится уникальным ключом пользователя.

После этого участник вступает в группу с ближайшим к своему ключом. Чтобы сделать это, он предоставляет группе пару ${\displaystyle (K_{public},Y)}$, после чего каждый участник группы проверяет выполнение всех условий, описанных в предыдущем параграфе, и сверяет ключ пользователя с ключом группы. Если в группе уже есть участник с таким ключом, то новый пользователь не принимается в группу (сделано для предотвращения "приглашений" в группу злоумышленников). Если же все подтвердили правильность ключа, то пользователю высылается случайно сгенерированный вектор ${\displaystyle V_{chal}}$, на который пользователь отвечает вектором ${\displaystyle V_{resp}=K_{private}(V_{chal})}$. Если группа подтверждает, что ${\displaystyle K_{public}(V_{resp})=V_{chal}}$, то пользователь принимается в группу.

Группы могут увеличиваться и уменьшаться, поэтому для обеспечения анонимности и быстродействия было решено, что размер группы должен быть больше ${\displaystyle k}$, но меньше ${\displaystyle 3k}$. Если размер группы стал меньше ${\displaystyle k}$, она немедленно распускается. Если размер группы стал больше ${\displaystyle 3k}$ и её участники согласны, она разделяется на две с новыми ключами ${\displaystyle K_{C1}}$ и ${\displaystyle K_{C2}}$, при этом:

• ${\displaystyle K_{C1}=K_{C_{prev}}+1/3(K_{C_{succ}}-K_{C_{prev}})}$
• ${\displaystyle K_{C1}=K_{C_{prev}}+2/3(K_{C_{succ}}-K_{C_{prev}})}$

где ${\displaystyle K_{C_{prev}}}$ - ключ предшествующей группы,${\displaystyle K_{C_{succ}}}$ - ключ следующей группы.

локальная топология

Внутри группы используется топология «звезда» (каждый с каждым). Для более быстрой работы для передачи каждого бита выбирается "центральный пользователь", которому все остальные передают результаты своих вычислений. Для балансировки нагрузки "центральный пользователь" меняется с каждой новой передачей. Подробнее смотреть документацию (англ.).

Если злоумышленники захватят группу, то они могут раскрыть анонимность последнего честного участника. Благодаря протоколу входа для группы размером 128, вероятность захватить более 90% группы составляет всего ${\displaystyle \sim 1{,}5\times 10^{-6}}$.

Если каждая группа, в которую входил пользователь ${\displaystyle N}$ обращалась к одному и тому же сайту, можно сделать вывод, что это делал пользователь ${\displaystyle N}$.

Центральный пользователь может изменять отправляемые пакеты. Однако центральный пользователь постоянно меняется, что позволяет минимизировать ущерб.