Filtro de bloom

    Filtro de Bloom (Bloom Filter) es una estructura de datos que se puede utilizar para informar al usuario si un elemento en particular es parte de un conjunto.

    Un filtro de bloom es una estructura de datos que se puede utilizar para informar al usuario si un elemento en particular es parte de un conjunto. Aunque no puede decir con certeza si un elemento está en el conjunto, puede decir con certeza si el elemento no lo está.

    Creado por Burton Howard Bloom en 1970, los filtros Bloom son una oferta atractiva para una variedad de aplicaciones debido a su eficiencia en el uso del espacio. En algunas criptomonedas (sobre todo Bitcoin), juegan un papel integral en la Verificación de Pago Simplificada o SPV.

    Al usar un cliente SPV, los usuarios pueden interactuar con la red Bitcoin sin ejecutar un nodo completo . Los nodos completos vienen con ciertos requisitos de almacenamiento y computacionales que los hacen difíciles de manejar en dispositivos de baja potencia como los teléfonos inteligentes. Los clientes de SPV, por otro lado, simplemente consultan nodos completos para obtener información relevante para la (s) billetera (s) del usuario.

    La solución más sencilla para transmitir estos datos al usuario sería hacer que los nodos completos conozcan las claves del cliente, de modo que solo se les envíen las transacciones pertinentes. Evidentemente, esta es una solución insatisfactoria ya que se sacrificaría la privacidad del cliente. Por otro lado, descargar todas las transacciones solo para descartar la mayoría de ellas sería una pérdida de ancho de banda. Introduzca filtros Bloom.

    Ilustremos. Suponga que un cliente, Alice, tiene una transacción de alto valor que no quiere que Bob, que ejecuta un nodo completo, tenga en cuenta. Ella construye un filtro Bloom, que ilustraremos como una cuadrícula de 10×1:

    0-9 sin números resaltados
    0-9 sin números resaltados

    Pasa los datos de la transacción que le interesan a través de dos funciones hash diferentes, que generan dos números entre 0 y 9. Llamémoslos 4 y 7. Envía el filtro a Bob.

    0-9. 4 y 7 están resaltados
    0-9. 4 y 7 están resaltados

    Al mirar esta cuadrícula, no tiene idea de qué datos ha pasado Alice al filtro. Si tuvieras un conjunto en el que estuvieran contenidos los datos, podrías modificarlos y compararlos con el filtro; si hay una coincidencia, existe la posibilidad de que sea la información que Alice solicitó.

    Al mismo tiempo, es probable que haya muchas entradas que se asignarán a 4 y 7, por lo que Bob no puede determinar en qué parte de los datos está interesada Alice. Simplemente devuelve todas las coincidencias y Alice las filtra en su extremo.

    Esto es, por supuesto, una simplificación excesiva, pero demuestra el concepto: los filtros Bloom ofuscan los verdaderos intereses del cliente. No es un método perfecto (todavía existen preocupaciones sobre su privacidad ), pero es una mejora con respecto a una solicitud sin blindaje a un nodo.

    « Regresa al diccionario