# Идеи по реализации gossip

## Bitcoin gossip

### Описание алгоритма

В данном разделе мы рассмотрим протокол распространения блоков
до внедрения BIP-152. BIP-152 снижает нагрузку на сеть путем
отказа от передачи блока целиком. Большинство транзакций в
передаваемом блоке и так известны получателю до того, как блок
будет ему передан. В нашем случае у нас нет мемпула, и такой
алгоритм не применим.

Протокол устроен следующим образом. Узлы уведомляют соседние узлы о появлении нового блока один раз после того, как сами его подтвердили. Для этого узел посылает inventory message (inv) всем подключенным в данный момент узлам. Inv message включает в себя хеши блоков, которые доступны для передачи.

Когда узел получает inv message для блока или транзакции, которых у него нет, он отвечает сообщением getdata, которое содержит соотвтствующий хеш.

Отправляющий узел при получении сообщения getdata посылает запрашиваемый блок или транзакцию получателю.

### Идеи по применению

Потенциальные проблемы и подходы к решению:

- У нас нет понятия активных соединений из-за UDP, но можно считать активными узлами тех, кто недавно отвечал на ping.
- Узел должен хранить историю анонсов, чтобы повторно не распространять анонс. Историю анонсов можно хранить в памяти в виде фильтров Bloom или Cuckoo.
- Пакеты могут теряться.
- Следует предусмотреть защиту от атак.

## BitTorrent DHT

### Описание алгоритма

В BitTorrent реализовано хранение информации о узлах сети (таблицы маршрутизации) через distributed hash table (DHT).
Протокол основан на Kademlia и работает по UDP, описан в [BEP_0005](http://www.bittorrent.org/beps/bep_0005.html).

Суть алгоритма в том, что каждый узел получает ID в пространстве ключей 0..2^160 (sha-1), это же пространство ключей используется и для infohash торрентов. Вводится XOR метрика, позволяющая сравнивать "расстояния" между ID узлов, а также между ID узла и infohash. Каждый узел хранит некоторое количество близких и далеких узлов в виде специальной структуры "K-buckets", так что поиск нужного узла сходится за O(log n). Поиск узла происходит итеративно, узел спрашивает известные ему узлы о все более близких к желаемому infohash. Узлы ближайшие к конкретному infohash хранят и обновляют список пиров, которые скачивают этот торрент.

### Идеи по применению

Это не gossip как таковой, но тоже может помочь решить некоторые задачи.
Мы могли бы тоже использовать подобный протокол для поиска нужных данных в сети. В том числе для peer discovery, как в Ethereum, там применяется тот же протокол Kademlia, но с некоторыми модификациями.