4.3 KiB
Идеи по реализации 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.
Суть алгоритма в том, что каждый узел получает ID в пространстве ключей 0..2^160 (sha-1), это же пространство ключей используется и для infohash торрентов. Вводится XOR метрика, позволяющая сравнивать "расстояния" между ID узлов, а также между ID узла и infohash. Каждый узел хранит некоторое количество близких и далеких узлов в виде специальной структуры "K-buckets", так что поиск нужного узла сходится за O(log n). Поиск узла происходит итеративно, узел спрашивает известные ему узлы о все более близких к желаемому infohash. Узлы ближайшие к конкретному infohash хранят и обновляют список пиров, которые скачивают этот торрент.
Идеи по применению
Это не gossip как таковой, но тоже может помочь решить некоторые задачи. Мы могли бы тоже использовать подобный протокол для поиска нужных данных в сети. В том числе для peer discovery, как в Ethereum, там применяется тот же протокол Kademlia, но с некоторыми модификациями.