Códigos: esconder, comprimir y proteger un mensaje

El cifrado de César sustituye cada letra de un mensaje por la que está un número fijo de puestos más adelante en el alfabeto, y el cifrado de Vigenère hace lo mismo pero cambiando el desplazamiento letra a letra según una palabra clave. El primero lo usaba Julio César para su correspondencia, según cuenta Suetonio, con un desplazamiento de tres; el segundo se consideró irrompible durante trescientos años y lo llamaron le chiffre indéchiffrable. Los dos caen ante la misma arma, la estadística de la lengua, y la manera en que caen es la primera lección de la criptografía: un cifrado no es seguro porque nadie sepa cómo funciona, sino porque saberlo no sirve de nada sin la clave.

El cifrado de César es fácil de romper por dos motivos, y la figura muestra los dos. El primero es que solo hay veinticinco claves posibles —veinticinco desplazamientos distintos—, así que se pueden probar todas y quedarse con la que produce castellano. El segundo es más profundo y sobrevive a los cifrados con muchas más claves: el desplazamiento no cambia la forma del texto, solo la etiqueta de cada letra. En español, la E es el 13,7 % de las letras, la A el 12,5 %, la O el 8,7 %, y así hasta la W, que no llega al 0,01 %. Un texto cifrado con César tiene las mismas proporciones con los nombres cambiados: la letra más frecuente del criptograma es, casi seguro, la E, y la distancia entre ambas es la clave. El histograma de la figura lo hace ver a simple vista: las barras del texto cifrado son las del español, corridas. El filósofo y matemático árabe al-Kindi lo explicó en el siglo IX en un tratado que se dio por perdido hasta 1987, y su método, el análisis de frecuencias, es la razón de que todos los cifrados por sustitución simple —incluidos los que usan un alfabeto desordenado, con 26! claves posibles, un número de veintisiete cifras— se rompan con un lápiz y una tarde.

La respuesta a al-Kindi tardó seiscientos años y fue el cifrado polialfabético: usar no un alfabeto de sustitución sino varios, y cambiar de uno a otro con cada letra. Leon Battista Alberti lo propuso en 1467 con un disco de dos coronas giratorias; Johannes Trithemius lo sistematizó en 1508 en una tabla cuadrada con los veintiséis alfabetos desplazados; Giovan Battista Bellaso publicó en 1553 la idea de elegir el alfabeto de cada letra con una palabra clave que se repite, que es lo que hoy se llama cifrado de Vigenère; y Blaise de Vigenère, diplomático francés, lo describió en su Traicté des chiffres de 1586 junto con una variante más fuerte que sí era suya, en la que la clave es el propio mensaje. El nombre se le quedó por error de los historiadores del siglo XIX. El efecto se ve al pulsar el botón de la figura: con la clave «QUIJOTE», la A del texto sale unas veces como Q, otras como U, otras como I, y el histograma del criptograma se aplana. Contar letras ya no delata a nadie. Durante tres siglos se creyó que eso bastaba.

No bastaba, y la razón está en la palabra que se repite. Si la clave tiene siete letras, las letras del mensaje que ocupan las posiciones 1, 8, 15, 22… se han cifrado todas con la misma letra de la clave, es decir, con el mismo César. Basta con adivinar la longitud de la clave, separar el criptograma en siete columnas y romper cada columna por frecuencias como si fuera César. Charles Babbage lo consiguió hacia 1854 y no lo publicó, quizá por interés militar en plena guerra de Crimea; el oficial prusiano Friedrich Kasiski lo publicó en 1863, con un método para averiguar la longitud —buscar trozos repetidos en el criptograma, que suelen estar a una distancia múltiplo de la longitud de la clave— y con ello el cifrado indescifrable dejó de serlo. La figura usa una herramienta posterior, más elegante, la que William Friedman propuso en 1922 y con la que empezó la criptografía matemática: el índice de coincidencia, la probabilidad de que dos letras tomadas al azar de un texto sean iguales. En un texto en español vale 0,077, porque las letras frecuentes coinciden mucho; en un texto en el que todas las letras fueran igual de probables valdría 1/26, 0,038. Un criptograma de Vigenère, bien mezclado, se acerca a 0,04; pero si se parte en columnas con la longitud correcta, cada columna es un César del español y su índice vuelve a 0,077. Las barras de la derecha de la figura calculan el índice para longitudes de 1 a 12: la longitud verdadera sobresale, y el botón «Romper» la usa para recuperar la clave letra a letra.

La única variante que resiste es la que Vigenère intuyó y Gilbert Vernam patentó en 1917: una clave tan larga como el mensaje, aleatoria y usada una sola vez. Con ella no hay columnas que separar, cada letra del criptograma es igual de probable que cualquier otra y Claude Shannon demostró en 1949 que el criptograma no contiene ninguna información sobre el mensaje. La libreta de un solo uso es perfectamente segura y perfectamente impráctica, porque la clave hay que hacerla llegar al destinatario por un canal tan seguro como el que se quería proteger, y ese problema —cómo compartir un secreto con alguien a quien no se puede ver— es el que resuelve la clave pública. Entre medias quedan las dos lecciones de la figura: que la estructura de la lengua se filtra a través de cualquier sustitución, y que una clave que se repite es una clave que se rompe.

La codificación de Huffman es el método para escribir un texto con el menor número de bits posible dando a cada símbolo un código de longitud fija para ese símbolo: cortos para los símbolos frecuentes, largos para los raros. David Huffman la inventó en 1951 siendo estudiante de doctorado en el MIT, para librarse de un examen final, y demostró que ningún otro código de ese tipo puede ser más corto. Es la pieza final de casi todos los compresores que se usan hoy —ZIP, gzip, PNG, JPEG, MP3— y la manera más clara de ver una idea que Claude Shannon había demostrado tres años antes: que la información de un mensaje se mide en la sorpresa de sus símbolos, y que la compresión consiste en gastar bits donde hay sorpresa y ahorrarlos donde no.

La idea de dar signos cortos a lo frecuente es anterior a la teoría. Samuel Morse y Alfred Vail, al diseñar su código en 1838, fueron a una imprenta de Morristown y contaron cuántos tipos de cada letra tenía el cajista: había doce mil de la E y solo doscientos de la Z. A la E le dieron un punto; a la Z, dos rayas y dos puntos. El código Morse no es óptimo —los operadores necesitaban pausas entre letras, que son un tercer símbolo escondido— pero encierra la intuición correcta. Lo que faltaba era la teoría de a cuánto se puede aspirar y el procedimiento para conseguirlo.

La teoría la puso Shannon en 1948. La cantidad de información de un símbolo es el logaritmo del inverso de su probabilidad: un símbolo que aparece la mitad de las veces aporta un bit, uno que aparece una de cada mil veces aporta casi diez. La media de esa cantidad sobre todos los símbolos, ponderada por su frecuencia, es la entropía de la fuente, y Shannon demostró que es el número medio de bits por símbolo por debajo del cual ningún código sin pérdidas puede bajar, y al que se puede acercar tanto como se quiera. Para un texto en castellano, contando letras sueltas, la entropía ronda los cuatro bits por letra, frente a los cinco que hacen falta para numerar veintisiete letras y a los ocho de ASCII. Shannon dio también un código que se acercaba al límite, con Robert Fano, pero no era el mejor posible, y Fano puso a sus estudiantes del MIT a buscar el óptimo como trabajo de curso, ofreciendo librar del examen a quien lo encontrara. Él mismo no sabía si existía.

Huffman lo encontró en el otoño de 1951, después de meses de intentos fallidos y, según contó cuarenta años después, justo cuando había decidido tirar los apuntes y estudiar para el examen. La solución consiste en construir el código al revés de como lo habían intentado todos: en lugar de repartir los bits de arriba abajo, empezando por separar los símbolos en dos grupos de peso parecido, se empieza por abajo, por los dos símbolos menos frecuentes. Se cuentan las apariciones de cada símbolo. Se toman los dos con menos apariciones y se unen bajo un nodo nuevo cuyo peso es la suma de los dos. Se repite con el bosque resultante —el nodo nuevo compite con los demás como si fuera un símbolo más— hasta que solo queda un árbol. El código de cada símbolo es el camino desde la raíz hasta su hoja, con un cero por cada rama izquierda y un uno por cada derecha. La figura hace las fusiones una a una: los símbolos raros se funden primero y por eso acaban en lo más profundo, con códigos largos; los frecuentes se quedan cerca de la raíz.

El procedimiento tiene dos propiedades que lo hacen funcionar. La primera es que ningún código es prefijo de otro: como todos los símbolos son hojas, al leer bits de uno en uno se sabe con certeza dónde acaba cada símbolo sin necesidad de separadores, que era la pausa que le sobraba al Morse. La segunda es la optimalidad, que Huffman demostró en dos páginas de 1952: en cualquier código óptimo los dos símbolos menos frecuentes tienen la misma longitud y difieren solo en el último bit, así que se pueden tratar como uno solo sin perder nada, y el argumento se repite hacia arriba. El código resultante gasta, de media, menos de un bit por símbolo por encima de la entropía, y la figura permite comprobarlo con cualquier texto: para la frase inicial del Quijote, alrededor de cuatro bits por carácter frente a los cinco del código fijo y los ocho de ASCII, con la entropía a pocas centésimas por debajo.

Ese bit de más es la limitación del método, y de él salieron los que le siguieron. Huffman asigna a cada símbolo un número entero de bits, y un símbolo con probabilidad 0,9 —que debería costar 0,15 bits— cuesta uno entero; la codificación aritmética de los años setenta y ochenta esquiva el problema codificando el mensaje completo como un único número, y se acerca a la entropía tanto como se quiera. Y Huffman mira los símbolos de uno en uno, cuando en un texto real la información está en las secuencias: después de una Q viene una U casi seguro. Jacob Ziv y Abraham Lempel publicaron en 1977 el algoritmo que sustituye las repeticiones por referencias a lo ya visto, y la combinación de los dos métodos —Lempel-Ziv para las repeticiones, Huffman para lo que queda— es el formato deflate de ZIP, gzip y PNG, que desde 1993 comprime buena parte de lo que circula por internet. En JPEG y MP3 el trabajo duro lo hace la parte con pérdidas, que decide qué no se verá ni se oirá, y Huffman remata empaquetando lo que sobrevive.

La figura pide poco y da mucho a cambio, y eso resume por qué el método ha durado setenta años: es exacto, es rápido, es óptimo en su clase y se explica con un dibujo. Lo que Huffman inventó para no examinarse describe algo que hacen las lenguas por su cuenta —las palabras más frecuentes son las más cortas, como muestra la ley de Zipf— y que el código Morse ya intuía: la eficiencia consiste en no gastar en lo esperado. El siguiente artículo, sobre el código de Hamming, hace lo contrario a propósito: añade bits que sobran para que el mensaje sobreviva a los errores.

El código de Hamming es la manera de enviar un mensaje de forma que, si un bit se estropea por el camino, el receptor no solo se dé cuenta sino que sepa cuál fue y lo repare, sin pedir que se repita nada. Lo consigue añadiendo unos pocos bits redundantes calculados con una astucia: a un mensaje de cuatro bits le bastan tres de comprobación, siete en total, para localizar cualquier error único entre los siete. Richard Hamming lo inventó en 1947 en los Laboratorios Bell por un motivo muy concreto —una máquina que tiraba su trabajo de fin de semana a la basura— y con ello fundó la teoría de los códigos correctores, que hoy está en cada disco duro, cada módulo de memoria, cada llamada de móvil y cada foto enviada desde una sonda espacial.

La historia la contó el propio Hamming muchas veces. En los Laboratorios Bell, los cálculos se hacían en máquinas de relés que leían tarjetas perforadas, y los investigadores como él, sin prioridad, tenían las máquinas los fines de semana. La máquina detectaba los errores —ya usaba un bit de paridad, que avisa cuando el número de unos de una palabra no es el esperado— pero al detectar uno se limitaba a abandonar el trabajo y pasar al siguiente. Dos fines de semana seguidos Hamming encontró el lunes que su cálculo se había interrumpido en la primera hora. «Si la máquina puede saber que hay un error, ¿por qué no puede saber dónde está y arreglarlo?», se preguntó, y la respuesta le ocupó los dos años siguientes. El artículo salió en 1950, con retraso porque Bell quiso patentarlo primero.

El truco está en dónde se colocan los bits de comprobación, y la figura lo hace visible. Se numeran las siete posiciones del 1 al 7. Los bits de paridad van en las posiciones que son potencias de dos, la 1, la 2 y la 4; los cuatro bits de datos, en las demás. El primer bit de paridad vigila todas las posiciones cuyo número, escrito en binario, tiene un 1 en el último lugar: la 1, la 3, la 5 y la 7. El segundo vigila las que tienen un 1 en el penúltimo: 2, 3, 6 y 7. El tercero, las que lo tienen en el antepenúltimo: 4, 5, 6 y 7. Cada paridad se ajusta para que el número de unos de su grupo sea par. Al recibir la palabra, el receptor rehace las tres comprobaciones. Si las tres cuadran, no ha habido error. Si alguna falla, se escribe un 1 por cada comprobación fallida y un 0 por cada correcta, en orden, y ese número binario —el síndrome— es la posición exacta del bit estropeado. Un error en la posición 6, que es 110 en binario, hace fallar la segunda y la tercera comprobación y no la primera; el síndrome 110 dice «6». Se voltea ese bit y el mensaje sale intacto. Los tres círculos de la figura son la misma idea dibujada: cada bit de datos está en la intersección de los círculos que lo vigilan, y los círculos que se ponen en naranja se cortan justo en el culpable.

El código tiene un límite, y la figura lo muestra en cuanto se estropean dos bits. El síndrome sigue señalando una posición, pero es la equivocada: el receptor «corrige» un bit sano y entrega un mensaje falso con toda confianza. La razón es una noción geométrica que Hamming introdujo en el mismo artículo y que lleva su nombre, la distancia: el número de bits en que difieren dos palabras. Las dieciséis palabras válidas del código (7,4) están todas a distancia tres o más unas de otras; un error las aleja una unidad de la palabra original y las deja aún a dos de cualquier otra, así que la más cercana es la correcta; con dos errores la palabra recibida queda a distancia uno de alguna otra palabra válida y el receptor la elige. Añadir un octavo bit que sea la paridad de los otros siete —el código (8,4) del segundo botón— no permite corregir dos errores, pero sí distinguir si ha habido uno o dos, y en el segundo caso pedir un reenvío en lugar de inventar. Es el compromiso que todo código tiene que elegir: cuántos bits de más enviar a cambio de cuántos errores corregir o detectar, y el botón que envía dos mil mensajes por un canal con ruido permite ver cómo cambia la cuenta según lo ruidoso que sea el canal.

Claude Shannon, en el despacho de al lado, había demostrado dos años antes algo que parecía imposible y que el código de Hamming hacía tangible: que por un canal con ruido se puede transmitir sin errores a una velocidad distinta de cero, siempre que se envíe redundancia bien elegida y no se pase de cierta capacidad. Shannon dijo qué era posible sin decir cómo; Hamming dio el primer cómo. Los que siguieron fueron más potentes y menos evidentes. Los códigos de Reed y Solomon de 1960 tratan los datos como coeficientes de un polinomio y corrigen ráfagas de errores consecutivos, y por eso están en los CD, donde una raya del disco borra miles de bits seguidos, en los códigos QR, que se leen con la mitad tapada, y en las sondas Voyager. Las memorias RAM de los servidores llevan una extensión del propio Hamming que corrige un bit y detecta dos, exactamente el código (8,4) de la figura a mayor escala. Y los códigos de comprobación de paridad de baja densidad que llevan el 5G y el wifi moderno rozan el límite de Shannon a costa de una decodificación que solo un ordenador puede hacer.

Hamming veía en su código algo más que una herramienta. En las conferencias que dio al final de su vida, recogidas en El arte de hacer ciencia e ingeniería, insistía en que la lección no era el código sino la pregunta: dejar de aceptar que la máquina se detuviera y preguntarse qué hacía falta para que no lo hiciera. La figura conserva esa pregunta. Un bit que cambia por el camino es un hecho del mundo, inevitable; que el mensaje llegue bien de todas formas es una decisión de diseño, y cuesta exactamente tres bits de cada siete. El resto del itinerario mira el otro lado del problema: qué pasa cuando el que cambia los bits no es el ruido sino un adversario, y para eso está la clave pública.

La criptografía de clave pública resuelve el problema que ningún cifrado anterior había podido resolver: cómo dos personas que nunca se han visto y que solo pueden hablar por un canal que todo el mundo escucha acuerdan un secreto. Durante dos mil años, desde el cifrado de César hasta la libreta de un solo uso, cifrar exigía compartir antes una clave, y compartir la clave exigía un mensajero, una valija, un encuentro. En 1976 Whitfield Diffie y Martin Hellman mostraron que no hacía falta: dos personas podían intercambiar números a la vista de todos y acabar con un secreto común que ningún oyente puede calcular. Sin ese hallazgo no existiría el comercio electrónico, ni la banca en línea, ni la mensajería cifrada, ni el candado que aparece en el navegador.

El problema se entiende con el caso más famoso de la Primera Guerra Mundial. En enero de 1917 el ministro alemán Arthur Zimmermann envió un telegrama a México proponiendo una alianza contra Estados Unidos, cifrado con un código de libro: cada palabra o sílaba era un grupo de cifras que había que buscar en un volumen que solo tenían las embajadas. Los británicos lo descifraron porque tenían copias parciales del libro, obtenidas de un barco hundido y de un agente en Persia. El código era bueno; lo que falló fue la distribución de la clave. Y esa es la debilidad estructural de toda la criptografía clásica: cuanto más gente necesita comunicarse en secreto, más claves hay que repartir por adelantado y más ocasiones de que una caiga en manos ajenas. Un ejército puede permitirse mensajeros; una red de millones de personas que compran, cobran y hablan entre sí, no.

La solución de Diffie y Hellman se apoya en una operación fácil de hacer y difícil de deshacer. Se elige un número primo p y un número g menor que él, los dos públicos. Alicia elige en secreto un número a y envía a Benito g elevado a a módulo p, es decir, el resto de dividir esa potencia entre p. Benito hace lo mismo con su secreto b. Cada uno eleva lo que ha recibido a su propio secreto, y los dos obtienen el mismo número, g elevado a a por b módulo p, porque el orden en que se elevan las potencias no importa. Eva, que ha oído p, g y las dos potencias, tendría que recuperar a a partir de g elevado a a: el logaritmo discreto. Con los números de dos cifras de la figura se hace probando, y el contador de Eva dice cuántas multiplicaciones necesita. Con el primo de siete cifras sigue siendo poco. Con los primos de seiscientas cifras que se usan hoy, no se conoce ningún método que termine en un tiempo comparable a la edad del universo, mientras que las potencias que calculan Alicia y Benito se hacen en milisegundos. La seguridad no está en que Eva no sepa cómo funciona el sistema —el sistema es público— sino en una asimetría de esfuerzo: multiplicar es barato y deshacer la multiplicación es caro.

Diffie y Hellman propusieron también, sin conseguir construirlo, algo más ambicioso: un cifrado en el que la clave para cerrar y la clave para abrir fueran distintas, de modo que una pudiera publicarse. Ron Rivest, Adi Shamir y Leonard Adleman lo construyeron en 1977, en el MIT, después de un año de intentos —Rivest cuenta que la idea le llegó una noche tras una cena de Pésaj— y se llama RSA por sus iniciales. Se toman dos primos grandes, p y q, y se publica su producto n junto con un exponente e. Cualquiera puede cifrar un mensaje m calculando m elevado a e módulo n. Para descifrar hace falta un exponente d que solo se puede calcular conociendo p y q por separado, y obtenerlos a partir de n es factorizar, el otro problema fácil de plantear y difícil de resolver de la aritmética. La tabla de la figura hace RSA con primos de dos cifras y muestra cada número: el cifrado, el descifrado que devuelve exactamente el mensaje, y las divisiones que necesita Eva para romperlo. Con un n de 617 cifras, el estándar actual, la mayor factorización conseguida hasta hoy se queda muy lejos.

La clave pública trajo algo que la criptografía clásica no tenía: la firma. Si Alicia cifra un mensaje con su clave privada, cualquiera puede descifrarlo con su clave pública, y el hecho de que salga algo con sentido demuestra que lo cifró ella y nadie más. Eso es una firma digital, y con ella se resuelve el problema que ni Diffie-Hellman resuelve por sí solo: saber que el g elevado a b que llega viene de Benito y no de Eva haciéndose pasar por él. Los certificados que hay detrás del candado del navegador son firmas encadenadas: una autoridad firma la clave pública de un sitio web, y el navegador trae de fábrica las claves de las autoridades. En la práctica, los sistemas actuales usan la clave pública solo para acordar un secreto y firmar, y cifran el grueso del tráfico con un cifrado simétrico rápido con la clave acordada, porque las potencias de seiscientas cifras son lentas.

Dos notas para terminar. La primera es que el descubrimiento se hizo dos veces. James Ellis, Clifford Cocks y Malcolm Williamson, del servicio de cifrado británico GCHQ, habían encontrado entre 1970 y 1974 tanto la idea general como el equivalente de RSA y el de Diffie-Hellman, y no pudieron publicarlo; se supo en 1997, cuando el GCHQ desclasificó los informes. Ralph Merkle, estudiante en Berkeley, había propuesto en 1974 una manera distinta de acordar una clave en público, que su profesor rechazó como trabajo de curso, y que se publicó en 1978. La segunda es que la asimetría de esfuerzo es un hecho empírico, no un teorema: nadie ha demostrado que factorizar o calcular logaritmos discretos sea difícil, solo que nadie sabe hacerlo deprisa con los ordenadores que existen. Peter Shor demostró en 1994 que un ordenador cuántico suficientemente grande haría las dos cosas en un tiempo razonable, y por eso desde 2016 se estandarizan cifrados «poscuánticos» basados en otros problemas. La figura sirve también para eso: recorrer los primos de la lista hacia arriba y ver cómo crece el trabajo de Eva es ver, en pequeño, la apuesta sobre la que descansa toda la seguridad de internet.

La tabla hash es la estructura de datos que permite guardar y encontrar cosas por su nombre en un tiempo que no depende de cuántas cosas haya. Es lo que hay detrás de los diccionarios de Python, los objetos de JavaScript, los índices de las bases de datos en memoria y las cachés de casi cualquier programa. La idea es de una audacia que sigue sorprendiendo cuando se ve por primera vez: en lugar de buscar la clave comparándola con las que ya hay, se calcula a partir de la propia clave, con una fórmula, el lugar donde debería estar, y se va directamente allí. La fórmula es la función hash; el lugar, una cubeta de un vector; y el problema que da lugar a toda la teoría es qué hacer cuando dos claves distintas caen en la misma cubeta, que es inevitable y se llama colisión.

La figura de esta página es una tabla hash con las cubetas a la vista. Cada palabra que se inserta pasa por la función hash elegida, el resultado se divide por el número de cubetas, y el resto dice en cuál cae. Con el método de encadenamiento, cada cubeta es una lista y las palabras que colisionan se apilan en ella; buscar una palabra es ir a su cubeta y recorrer la lista. Con el de direccionamiento abierto, cada cubeta guarda una sola palabra, y la que encuentra la suya ocupada avanza a la siguiente libre; buscar es ir a la cubeta y avanzar hasta encontrar la palabra o un hueco vacío. Los dos métodos son de los años cincuenta: Arnold Dumey publicó el primero en 1956, con la observación de que un resto de división reparte bien las claves, y Wesley Peterson analizó el segundo en 1957 para los discos de IBM.

Lo que la figura enseña primero es que la función hash lo es todo. La suma de los códigos de las letras es una función hash legítima —siempre da el mismo número para la misma palabra— y es pésima: las palabras de longitud parecida suman cantidades parecidas y caen en cubetas vecinas, dos anagramas caen en la misma, y con dieciséis cubetas la mayoría de las palabras acaban en tres o cuatro de ellas mientras el resto quedan vacías. Una función buena, como FNV-1a, mezcla cada letra con las anteriores de manera que cambiar una sola letra cambia el resultado entero de forma impredecible, y las palabras se reparten como si se hubieran lanzado al azar. Esa es la propiedad que se pide: no que la función sea aleatoria, sino que se comporte como si lo fuera. Lawrence Carter y Mark Wegman demostraron en 1979 que eligiendo la función hash al azar de una familia adecuada se garantiza ese comportamiento para cualquier conjunto de claves, incluso uno elegido por un adversario, lo que hoy importa porque una tabla hash con una función predecible se puede atacar llenándola de colisiones a propósito.

Lo segundo es el factor de carga, la fracción de cubetas ocupadas, que la figura llama α. Con encadenamiento, si las claves se reparten bien, la longitud media de una lista es α y buscar una clave que está cuesta de media 1 + α/2 comparaciones; con α = 2 son dos, con α = 10 son seis, y la tabla degenera en una lista corriente. Con direccionamiento abierto la cosa es más brusca: Donald Knuth calculó en 1963, en el que cuenta como su primer análisis de un algoritmo, que buscar con sondeo lineal cuesta de media ½(1 + 1/(1 − α)) sondeos, que vale 1,5 con la tabla medio llena, 3 al 80 % y 50 al 99 %. La figura reproduce esa curva: al insertar palabras en una tabla pequeña con direccionamiento abierto, los sondeos se disparan al llenarse, y llega un momento en que no cabe nada. Por eso las tablas reales se agrandan solas cuando α supera un límite, típicamente entre 0,7 y 0,9, copiando todo a un vector del doble de tamaño. Esa copia cuesta, pero se hace pocas veces, y repartida entre todas las inserciones sale a coste constante.

Lo tercero es qué significa «tiempo constante». Una tabla hash no promete que cada búsqueda cueste lo mismo; promete que el promedio no crece con el número de claves, siempre que la función reparta bien y la carga se mantenga a raya. La peor búsqueda posible puede recorrer todas las claves, y hay variantes, como el hashing cuco de Rasmus Pagh y Flemming Rodler de 2004, que garantizan como mucho dos sondeos en cualquier búsqueda a cambio de una inserción más complicada. Pero el promedio es lo que hace útil la estructura, y es lo que la hace distinta de los árboles de búsqueda, que garantizan un coste logarítmico en el peor caso a cambio de no alcanzar nunca el constante.

La tabla hash es también un buen ejemplo de una idea que reaparece en toda la informática: cambiar orden por aleatoriedad. Un vector ordenado permite buscar en tiempo logarítmico porque el orden dice hacia dónde ir; una tabla hash renuncia al orden —sus claves no se pueden recorrer de menor a mayor— y a cambio va directa. La figura muestra esa renuncia en el desorden de las cubetas: las palabras están donde su hash las mandó, sin relación con su alfabeto ni con su llegada. Es la misma apuesta que hacen el filtro de Bloom y buena parte de los algoritmos probabilistas: aceptar que el peor caso exista, y organizar las cosas para que casi nunca ocurra.

El filtro de Bloom es una estructura de datos que responde a la pregunta «¿he visto ya este elemento?» usando una cantidad de memoria ridícula, a cambio de equivocarse a veces en una sola dirección. Nunca dice que no ha visto algo que sí vio. Puede decir que ha visto algo que no vio, con una probabilidad pequeña y calculable. Esa asimetría lo hace perfecto como portero: antes de hacer una operación cara —consultar un disco, preguntar a otro servidor, buscar en una lista de millones de direcciones maliciosas—, se pregunta al filtro, y si dice «no» se ahorra la operación con toda seguridad; si dice «quizá», se hace la operación y se comprueba. Burton Bloom lo propuso en 1970 en cuatro páginas, y hoy está en los navegadores, en las bases de datos, en los routers y en las criptomonedas.

La figura de esta página es un filtro de Bloom entero, bit a bit. La rejilla de la izquierda es un vector de m bits, todos a cero al principio. Insertar una palabra es pasarla por k funciones hash distintas, que dan k posiciones del vector, y poner a uno esos k bits. Consultar una palabra es calcular sus mismas k posiciones y mirar: si alguno de los bits está a cero, la palabra no se ha insertado, con certeza absoluta, porque de haberse insertado ese bit estaría a uno. Si todos están a uno, la palabra probablemente se insertó, pero puede que no: puede que otros elementos, entre todos, hayan encendido por casualidad esos k bits. Eso es un falso positivo, y el botón que consulta una palabra que no está permite ir a la caza de uno.

Lo primero que se ve es cuánto cabe. El vector de 256 bits de la figura ocupa 32 bytes, lo que ocuparían cinco o seis palabras cortas escritas tal cual, y sin embargo con tres funciones hash puede guardar la huella de cuarenta palabras y responder mal a menos del 10 % de las consultas sobre palabras ausentes. Con 1.024 bits y cien palabras, el error baja del 2 %. El filtro no guarda las palabras: no se pueden recuperar de él ni recorrer, solo preguntar por una. Esa es la renuncia que compra el ahorro, y el motivo de que el filtro complemente a otras estructuras en lugar de sustituirlas.

Lo segundo es la fórmula, que la gráfica de la derecha dibuja junto a la medida real. Tras insertar n elementos con k funciones en m bits, la fracción de bits que sigue a cero es aproximadamente e^(−kn/m), y la probabilidad de que una palabra ausente encuentre sus k bits encendidos es esa fracción de bits encendidos elevada a k. La medida de la figura, hecha con quinientas palabras que no están, sigue la curva teórica con el vaivén que corresponde a una muestra de ese tamaño. La fórmula dice también cuántas funciones conviene usar: con pocas, cada palabra deja poca huella y una ausente la imita fácilmente; con muchas, el vector se llena de unos y todo parece estar. El óptimo es k = (m/n)·ln 2, unas 0,7 funciones por cada bit disponible por elemento, y con él la tasa de error es 0,6185 elevado a m/n: con diez bits por elemento, menos del 1 %. La figura calcula el óptimo para el número de palabras insertadas y avisa cuando el k elegido se aleja.

Lo tercero es de dónde salen k funciones hash. Calcular ocho funciones distintas por cada consulta sería caro, y en la práctica no hace falta. Adam Kirsch y Michael Mitzenmacher demostraron en 2008 que basta con dos funciones, h₁ y h₂, y usar h₁ + i·h₂ para i de 0 a k − 1, sin que la tasa de falsos positivos empeore de forma apreciable. Es lo que hace la figura, con dos variantes de la función FNV, y es lo que hacen la mayoría de las implementaciones.

El filtro tardó treinta años en hacerse famoso, y lo que lo lanzó fue la red. Li Fan y sus colegas propusieron en 2000 que las cachés web de una organización se intercambiaran, en lugar de la lista completa de las páginas que cada una tenía, un filtro de Bloom de esa lista: una fracción de la memoria, y a cambio alguna consulta ocasional a una caché vecina que resultaba no tener la página. Andrei Broder y Michael Mitzenmacher recopilaron en 2004 decenas de usos en redes y acuñaron el principio del filtro de Bloom: siempre que una lista o un conjunto se usen y el espacio importe, considérese un filtro de Bloom si los falsos positivos se pueden tolerar. Bigtable, la base de datos de Google descrita en 2008, guarda un filtro por cada fichero en disco para no leer ficheros que no contienen la clave buscada, y la idea se copió en casi todos los almacenes de datos posteriores. Chrome usó durante años un filtro de Bloom con las direcciones peligrosas conocidas, para consultar al servidor solo cuando el filtro decía «quizá». Bitcoin lo usa para que un cliente ligero pida a la red solo las transacciones que le pueden interesar sin revelar cuáles son.

Hay una limitación que la figura hace visible: no se puede borrar. Poner a cero los bits de una palabra apagaría también los de otras que los compartan, y el filtro empezaría a dar falsos negativos, lo único que prometía no dar. Las variantes con contadores en lugar de bits lo permiten a cambio de más memoria. Pero la versión original, la de 1970, sigue siendo la que se usa cuando lo que hay que recordar solo crece, y su lección va más allá del caso: hay preguntas cuya respuesta exacta cuesta mucho y cuya respuesta casi exacta, con el error en la dirección correcta, cuesta casi nada.