Mastering Bitcoin
8. La Red Bitcoin » Filtros Bloom
Página 55 de 98
Filtros Bloom
Un filtro bloom es un filtro de búsqueda probabilística, una manera de describir un patrón deseado sin especificarlo exactamente. Los filtros bloom ofrecen una forma eficiente de expresar un patrón de búsqueda al mismo tiempo que se protege la privacidad. Se utilizan por los nodos SPV para pedir a sus compañeros las transacciones que coincidan con un patrón específico, sin revelar exactamente qué direcciones están buscando.
En nuestra analogía anterior, un turista sin mapas está pidiendo direcciones a una dirección específica, «23 Church St». Si preguntara a extraños por las direcciones a esta calle, estaría inadvertidamente revelando su destino. Un filtro de bloom es como preguntar: «¿Hay calles en este barrio cuyos nombres terminen en R-C-H?» Una pregunta como esa revela un poco menos sobre el destino deseado que pedir directamente «23 Church St». Usando esta técnica, un turista puede especificar la dirección deseada con mayor detalle, como «que termine en R-C-H», o con menor detalle, como «que termine en H». Mediante la variación de la precisión de la búsqueda, el turista revela más o menos información, a expensas de obtener resultados más o menos específicos. Si el turista preguntara con un patrón menos específico, obtendría muchas más direcciones posibles y una mejor privacidad, pero muchos de los resultados serían irrelevantes. Si preguntara con un patrón muy específico, obtendría menos resultados, pero perdería privacidad.
Los filtros bloom consiguen cumplir esta función al permitir que un nodo SPV especifique un patrón de búsqueda para las transacciones que puede ajustarse hacia precisión o hacia privacidad. Un filtro bloom más específico producirá resultados precisos, pero a expensas de revelar las direcciones que se utilizan en la cartera del usuario. Un filtro de bloom menos específico producirá más datos sobre más transacciones, muchos irrelevantes para el nodo, pero permitirá que el nodo pueda mantener mejor la privacidad.
Un nodo SPV inicializará un filtro bloom como «vacío», es decir, no contendrá ningún patrón. Después, el nodo SPV hará una lista de todas las direcciones en su cartera y creará un patrón de búsqueda que coincida con la salida de transacción que corresponda a cada dirección. Por lo general, el patrón de búsqueda es un script pago-a-clave-pública-hash (P2PKH, pay-to-public-key-hash en inglés), que es el script de bloqueo que debería estar presente en cualquier transacción que pague a la clave-pública-hash (dirección). Si el nodo SPV está rastreando el saldo de una dirección P2SH, entonces el patrón de búsqueda será un pago-a-script-hash (pay-to-script-hash en inglés). Después, el nodo SPV añadirá cada uno de los patrones de búsqueda al filtro bloom, de manera que el filtro bloom pueda reconocer el patrón de búsqueda en el caso de que esté presente en alguna transacción. Finalmente, el filtro bloom se envía al compañero, que lo utiliza para encontrar transacciones que coincidan para ser transmitidas al nodo SPV.
Los filtros bloom se implementan como un vector (en inglés, «array») de tamaño variable de N dígitos binarios (un campo de un bit) y un número variable M de funciones hash. Las funciones hash están diseñadas para producir siempre una salida que está comprendida entre 1 y N, que corresponde al vector de dígitos binarios. Las funciones hash se generan de manera determinista, de modo que cualquier nodo que ejecute un filtro bloom siempre utilizará las mismas funciones hash y obtendrá los mismos resultados para una entrada específica. El filtro bloom puede ajustarse eligiendo diferentes longitudes (N) y un número diferente (M) de funciones de hash, variando así el nivel de precisión y por lo tanto la privacidad.
En un ejemplo de filtro bloom simple, con un campo de 16 bits y tres funciones hash, usamos un pequeño vector de 16 bits y un conjunto de tres funciones hash para demostrar cómo funcionan los filtros de Bloom.
Figura 8. Un ejemplo de filtro bloom simple, con un campo de 16 bits y tres funciones hash
El filtro bloom se inicializa para que el vector de bits sea todo ceros. Para agregar un patrón al filtro bloom, se hace hash del patrón, una vez para cada función hash. La aplicación de la primera función de hash a la entrada da como resultado un número entre 1 y N. Se localiza el bit correspondiente en el vector (indexado de 1 a N) y se pone a 1, quedando registrada así la salida de la función hash.
Entonces, se ejecuta la siguiente función hash para establecer otro bit, y así sucesivamente. Una vez de que se han aplicado todas las funciones de hash M, el patrón de búsqueda queda «registrado» en el filtro bloom como M bits que han cambiado de 0 a 1. Añadiendo un patrón «A» a nuestro filtro bloom simple es un ejemplo de la adición de un patrón «A» para el filtro bloom sencillo mostrado en Un ejemplo de filtro bloom simple, con un campo de 16 bits y tres funciones hash.
Añadir un segundo patrón es tan simple como repetir este proceso. Se hace hash del patrón mediante la ejecución cada una de las funciones hash, y el resultado se registra mediante el establecimiento de los bits a 1. Tenga en cuenta que a medida que un filtro bloom se llena con más patrones, algún resultado de la función de hash podría coincidir con uno que ya está marcado a 1, en cuyo caso no se cambia el bit. En esencia, la aparición de más patrones que se registren como bits superpuestos es la señal de que el filtro bloom comienza a saturarse con más bits establecidos en 1, haciendo que la precisión del filtro disminuya. Por ello, el filtro es una estructura de datos probabilística que se vuelve menos precisa a medida que se agregan más patrones. La precisión depende del número de los patrones agregados en relación con el tamaño del vector de bits (N) y el número de funciones hash (M).
Un vector de bits más grande y con más funciones hash puede registrar más patrones con mayor precisión. Un vector de bits más pequeño o con menos funciones hash registrará menos patrones y producirá menos precisión.
Figura 9. Añadiendo un patrón «A» a nuestro filtro bloom simple
Añadiendo un segundo patrón «B» a nuestro filtro bloom simple es un ejemplo que añade un segundo patrón «B» al filtro bloom simple.
Figura 10. Añadiendo un segundo patrón «B» a nuestro filtro bloom simple
Para probar si un patrón es parte de un filtro bloom, se hace hash del patrón con cada una de las funciones hash, y el patrón de bits resultante se chequea contra el vector de bits. Si todos los bits indexados por las funciones hash se establecen en 1, entonces el patrón está probablemente registrado en el filtro de Bloom. Debido a que los bits se pueden establecer debido a la superposición originada por múltiples patrones, la respuesta no es irrefutable, sino que es probabilística. En términos simples, un resultado positivo de filtro bloom es un «Tal vez, Sí».
Probando la existencia del patrón «X» en el filtro bloom. El resultado es una coincidencia positiva probabilística, es decir, «Tal vez». Es un ejemplo de pruebas de la existencia del patrón «X» en el filtro bloom simple. Los bits correspondientes se establecen en 1, por lo que el patrón es probablemente una coincidencia.
Figura 11. Probando la existencia del patrón «X» en el filtro bloom. El resultado es una coincidencia positiva probabilística, es decir, «Tal vez».
Por el contrario, si un patrón se prueba contra el filtro bloom y uno cualquiera de los bits se establece en 0, queda demostrado que el patrón no se registró en el filtro bloom. Un resultado negativo no es una probabilidad, es una certeza. En términos simples, un resultado negativo en un filtro bloom es un «¡Definitivamente No!» Testeando la existencia del patrón «Y» en el filtro bloom. El resultado es una coincidencia negativa definitiva, que significa «¡Definitivamente No!» es un ejemplo para probar la existencia del patrón «Y» en el filtro bloom simple. Uno de los bits correspondientes se establece en 0, por lo que el patrón es definitivamente una no coincidencia.
Figura 12. Testeando la existencia del patrón «Y» en el filtro bloom. El resultado es una coincidencia negativa definitiva, que significa «¡Definitivamente No!»
La aplicación de filtros bloom en Bitcoin se describe en la Propuesta de Mejora Bitcoin 37 (BIP0037). Consulte apartado sobre propuestas de mejora bitcoin o visite GitHub.