Что Такое Фильтр Блума?

Фильтр Блума, разработанный в 1970 году Бёртоном Говардом Блумом, информирует пользователей о том, принадлежит ли определённый предмет набору или нет. Но стоит помнить, что даже если обнаруживается, что предмет в наборе, результат не всегда верный.

Из-за своей эффективности в экономии места, фильтры Блума являются очень привлекательными для разнообразных применений. В мире крипто они повсеместно используются в Упрощённой Проверке Платежей (SPV), особенно в Биткоине.

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

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

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

Представьте, что Анна является клиентом, а Джон полным нодом. У Анны дорогая транзакция, но она не хочет, чтобы об этом узнал Джон. Поэтому ей нужно “замаскировать” её транзакцию. Для этого она создаёт фильтр Блума. Предположим, что он выглядит таким образом:

3 4 2 1 6 8 7 5 0 9

Она пропускает данные транзакции через две отдельных хэш функции. Каждая из этих функций выберет два значения из строки чисел выше. Давайте предположим, что это будет 2 и 8.

3 4 2 1 6 8 7 5 0 9

После этого Анна отправляет фильтр Джону. Очевидно, что нет никакой возможности узнать какие данные предоставила Анна только лишь по этому фильтру.

Однако Джон имеет весь набор, содержащий данные Анны, он может использовать хэш для поиска схожестей в фильтре. Если находится совпадение, то возможно, что эти данные просила Анна.

Однако несколько вводных указывают на 2 и 8. Поэтому Джон не сможет узнать в каких именно данных заинтересована Анна. Он вернёт все совпадения, из которых Анна выберет нужные.

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

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