Фильтр Блума

Фильтр Блума — это структура данных, которую можно использовать для информирования пользователя о том, является ли конкретный элемент частью набора. Хотя он не может с уверенностью сказать, находится ли элемент в множестве, он может с уверенностью сказать, что элемента нет.

Фильтры Блума, созданные Бертоном Ховардом Блумом в 1970 году, являются привлекательным предложением для целого ряда приложений благодаря их эффективности использования пространства. В некоторых криптовалютах (в первую очередь в биткойнах) они играют неотъемлемую роль в упрощенной проверке платежей или SPV.

При использовании клиента SPV пользователи могут взаимодействовать с сетью Биткойн, не запуская полный узел. Полные узлы имеют определенные требования к хранилищу и вычислительным ресурсам, которые делают их громоздкими для работы на маломощных устройствах, таких как смартфоны. Клиенты SPV, с другой стороны, просто запрашивают полные узлы для получения информации, относящейся к кошельку (кошелькам) пользователя.

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

Проиллюстрируем. Предположим, что у клиента, Алисы, есть крупная транзакция, о которой она не хочет, чтобы Боб, управляющий полным узлом, знал о ней. Она строит фильтр Блума, который мы проиллюстрируем в виде сетки 10x1:

Она передает интересующие ее данные транзакции через две разные хеш-функции, которые выводят два числа от 0 до 9. Назовем их 4 и 7. Она отправляет фильтр Бобу.

Глядя на эту сетку, вы не представляете, какие данные Алиса передала фильтру. Если бы у вас был набор, в котором содержались данные, вы могли бы их хэшировать и сравнить с фильтром — если есть совпадение, есть вероятность, что это была информация, которую запросила Алиса.

В то же время, вероятно, будет много входных данных, которые будут отображаться на 4 и 7, поэтому Боб не может определить, какая часть данных интересует Алису. Он просто возвращает все совпадения, а Алиса фильтрует их со своей стороны.

Это, конечно, грубое упрощение, но оно демонстрирует концепцию: фильтры Блума затемняют истинные интересы клиента. Это не идеальный метод (до сих пор есть опасения по поводу его конфиденциальности), но это улучшение по сравнению с незащищенным запросом к узлу.