Bloom filter

Начать серию статей про технологии я хотел не со стандартных блокчейнов и майнингов, а с чего-то более интересного но не описанного. Поэтому начну его с SPV технологии, потому что она сама по себе является довольно крутым примером того стека, который сейчас используется в криптовалютах.

Представьте ситуацию, когда есть зал, полный людей, и у каждого есть список телефонов всех кто сидит в зале. Вы можете дать задание всем людям на нахождение определенных номеров, но не хотите выдавать какие именно номера вам нужны. Именно эту задачу решает фильтр блума. Найти информацию внутри базы, но при этом не выдать провайдеру данных – какую именно информацию ты ищешь.

Реализуется это просто. Но для этого нужно немного пояснить про хеш функции. Вы наверно представляете хеш функции как что-то непонятное, на выходе генерирующее случайную строку, типо заголовка блока биткоина или транзакции? Но нет, на выходе хеш функции вы получаете число. В случае биткоинов и других криптовалют – это просто очень большое число, записывающееся в 16-ричном формате. Но хеш функции могут быть и проще. Они могут возвращать, к примеру маленькое число, от 0 до 50.

Для нашего примера – создадим функцию, которая складывает все цифры в номере телефона и берет целочисленные остаток от деления на 16. Это и будет пример простой хеш-функции. К примеру, для телефона 89039154242 это будет 47%16 = 15. Теперь построим ленту байт из 16 элементов и 15й элемент установим в 1. Далее добавим еще произвольные 2 хеш функции, например одна из них еще будет прибавлять 10 к сумме цифр, а вторая умножать на 255. Итого у нас получится 3 числа: 15, 9, 1. Эти 3 числа будут в ленте байт установлены в 1, остальные в 0. Теперь достаточно пройтись по всем телефонным номерам используя 3 этих хеша, и вернуть только те номера, которые подходят под фильтр, в котором 15 элемент равен 1, 9й элемент равен 1, и 1й элемент равен 1, а остальные равны 0.

Простота и гениальность фильтра блума в том, что тот, кто ищет информацию не знает, что именно он ищет, и даже если находит, не может точно сказать, что именно эта информация нужна клиенту. А всё потому, что фильтр блума отвечает на вопрос «подходит ли элемент фильтру?» не «да/нет», а «возможно/нет». Кроме этого фильтр позволяет уменьшать и увеличивать распределение вероятности, оперируя количеством хеш функций. Чем их больше, тем точнее результат.

В нашем примере, если все участники будут знать алгоритм хеширования, фильтр и параметры (количество функций хеширования) – то все без труда смогут найти необходимые телефонные номера из списка, но нам придется всё-таки проверять, что именно они нам нужны, так как существует избыточность.

В криптовалютах Фильтр блума используется в технологии SPV (simplified payment verification), которая упрощает и облегчает кошельки, которым больше не нужно ждать полной проверки блокчейна, потому что упрощенные кошельки отправляют полным доверенным нодам фильтр, содержащий все адреса и транзакции, связанные с вами и вашим кошельком. Далее полная нода обходит весь блокчейн, применяя фильтр к каждому блоку и полям транзакции, с целью найти блоки, которые облегченной ноде всё-таки необходимо будет проверить. И отправляет SPV кошельку специальное сообщение “merkleblock”, содержащее не полный блок со всеми транзакциями, а только с транзакциями, связанными с вашим фильтром. Суть этого сообщения в том, что тут используется merklebranch, который можно проверить с помощью merkleroot из заголовка блока. Суть этих действий в том, чтобы подтвердить, что транзакция действительно есть в блоке.

В итоге, вместо скачивания всего блокчейна, SPV нода скачивает 1% или менее от всего блокчейна и проверяет только эти блоки. При этом важно, чтобы полные ноды были доверенными, так как в противном случае SPV нода может быть обманута недобросовестным узлом сети.

В связи с ростом блокчейна криптовалют, Технология SPV будет входить в оборот всё чаще, и во все большем количестве монет будет появляться облегченные кошельки. Я уверен, что монеты нужно хранить в холодную, на кошельке, но не вижу смысла скачивать полные ноды лишь для оплат, и не особо доверяю сервисам, вроде blockchain.info, и другим онлайн кошелькам, где вы не полный хозяин своих ключей. Очевидным решением является использование SPV кошельков, которые и не скачивают полный блокчейн, и при этом ключи из которых, доступны только вам. Примером таких кошельков являются:

• Jaxx: btc, ltc, dash, eth, zcash
• Electrum: btc
• Electron cash: bch