Si alguna vez envió un mensaje de texto, reprodujo un CD o almacenó un archivo en la nube, se benefició de la corrección de errores. Esta idea revolucionaria se remonta a la década de 1940, cuando los investigadores se dieron cuenta por primera vez de que es posible reescribir cualquier mensaje de una forma que permita revertir fácilmente la corrupción posterior.

A lo largo de los años, los investigadores han desarrollado muchos esquemas ingeniosos, llamados códigos de corrección de errores, que codifican datos de diferentes maneras y utilizan diferentes procedimientos para corregir errores. Pero para los científicos informáticos teóricos, pocos son tan convincentes como los llamados códigos corregibles localmente. Estos códigos tienen dos propiedades simultáneas que suenan casi contradictorias: cualquier error se puede corregir leyendo los datos codificados en unos pocos lugares, pero ningún atacante puede frustrar este procedimiento de corrección alterando selectivamente el código. Es como si pudieras recuperar cualquier página arrancada de un libro con sólo echar un vistazo a algunas otras.

"Es un fenómeno bastante mágico", dijo Tom Gur, informático de la Universidad de Cambridge. "A priori, no es obvio que tal objeto matemático pueda existir en absoluto".

Pero esta magia tiene un alto coste. Los únicos ejemplos conocidos de códigos corregibles localmente son extremadamente ineficientes: codificar cualquier mensaje también lo hace exponencialmente más largo. Libros enteros codificados de esta manera serían demasiado difíciles de manejar.

Los informáticos se han preguntado durante mucho tiempo si son posibles mejores códigos corregibles localmente. Se han centrado especialmente en códigos que utilizan sólo tres consultas para corregir cualquier error, con la esperanza de que esta severa restricción pueda hacer que estos códigos sean más fáciles de entender. Pero incluso este simple caso ha dejado perplejos a los investigadores durante más de 20 años.

Ahora el informático Pravesh Kothari de la Universidad Carnegie Mellon y su estudiante de posgrado Peter Manohar finalmente tengo demostrado que es imposible crear un código de tres consultas corregible localmente que evite ese costo exponencial. Puede ser un resultado negativo, pero cualquier cosa que aclare los límites de la corrección de errores es apasionante para los investigadores, especialmente porque las matemáticas de los códigos corregibles localmente surgen en áreas muy alejadas de la comunicación.

"Este resultado es sorprendente", dijo Shubhangi Saraf, informático de la Universidad de Toronto. "Es un gran avance".

Strength in Numbers

Para comprender la corrección de errores, imagine los datos que desea proteger como una secuencia de bits, o 0 y 1. Un error, en este modelo, puede ser cualquier cambio no deseado de un 0 a un 1 o viceversa, ya sea debido a una fluctuación aleatoria o una manipulación deliberada.

Supongamos que desea enviar un mensaje a un amigo, pero le preocupa que los errores puedan cambiar el significado. Una estrategia simple es reemplazar cada 0 en su mensaje con 000 y cada 1 con 111. Si su amigo ve una parte del mensaje que no contiene tres bits idénticos seguidos, sabrá que se ha producido un error. Y si los errores son aleatorios y relativamente raros, entonces es mucho más probable que cualquier cadena de 110 sea un 111 corrupto que un 000 corrupto. Una mayoría simple de votos dentro de cada triplete será suficiente para corregir la mayoría de los errores.

Este esquema, llamado código de repetición, tiene la virtud de la simplicidad, pero poco más es recomendable. Por un lado, es necesario triplicar la longitud de cada mensaje sólo para hacer frente a errores relativamente poco frecuentes, y si existe una buena posibilidad de que se produzcan dos errores adyacentes, necesitaremos aún más redundancia. Peor aún, rápidamente se vuelve inútil si los errores no son aleatorios, como cuando los atacantes intentan sabotear activamente el código. En el código de repetición, toda la información necesaria para corregir un bit determinado se almacena en unos pocos bits más, lo que lo deja vulnerable a un ataque dirigido.

Afortunadamente, a muchos códigos de corrección de errores les va mejor. Un ejemplo famoso, llamado Código Reed-Solomon, funciona transformando mensajes en polinomios (expresiones matemáticas como x² + 3x + 2 que constan de diferentes términos sumados, cada uno con una variable (como x) elevado a una potencia diferente. Codificar un mensaje usando un código Reed-Solomon implica construir un polinomio con un término para cada carácter del mensaje, luego trazar el polinomio como una curva en un gráfico y almacenar las coordenadas de los puntos que se encuentran en la curva (tomando al menos un código más). punto que el número de caracteres). Los errores pueden sacar algunos de estos puntos de la curva, pero si no hay demasiados errores, solo una curva polinómica pasará por la mayoría de los puntos. Es casi seguro que esa curva corresponde al verdadero mensaje.

Los códigos Reed-Solomon son hipereficientes: sólo es necesario almacenar unos pocos puntos adicionales para corregir errores, por lo que cualquier mensaje codificado es sólo un poco más largo que el original. También son menos vulnerables al tipo de interrupción dirigida que significaría un desastre para el código de repetición, porque la información utilizada para corregir un error en cualquier lugar se distribuye a lo largo de todo el mensaje codificado.

Piensa globalmente actua localmente

La fuerza del código Reed-Solomon surge de la interconexión. Pero precisamente debido a esa interconexión, no hay manera de corregir un solo error en un mensaje codificado sin leerlo completo. Puede que eso no parezca un problema en el contexto de la comunicación: si estás enviando un mensaje, probablemente quieras que el destinatario lo lea todo. Pero puede ser un problema en el almacenamiento de datos, otra aplicación importante de la corrección de errores.

Considere una empresa que almacena los correos electrónicos de los usuarios en la nube, es decir, en una amplia gama de servidores. Puedes pensar en toda la colección de correos electrónicos como un mensaje largo. Ahora supongamos que un servidor falla. Con un código Reed-Solomon, necesitarías realizar un cálculo masivo que involucrara todos los datos codificados para recuperar tus correos electrónicos de ese servidor perdido. “Habría que mirarlo todo”, dijo Zeev Dvir, científico informático de la Universidad de Princeton. "Podrían ser miles de millones de correos electrónicos; podría llevar mucho tiempo".

Los investigadores utilizan el término "local" para describir códigos que utilizan sólo una fracción del mensaje codificado para detectar errores o corregirlos. El código de repetición simple tiene algo de este carácter local, pero eso es precisamente lo que lo hace tan vulnerable a la manipulación. Por el contrario, un código corregible localmente obtiene lo mejor de ambos mundos: puede corregir un error en cualquier parte con solo unas pocas consultas, todo sin perder la interconexión que hace que los códigos Reed-Solomon sean tan resistentes.

"Esta es una noción realmente estricta", dijo Kothari.

Los ejemplos más famosos de códigos corregibles localmente son versiones de un venerable código de corrección de errores inventado en 1954 por los matemáticos. david müller y caña de irving (quien también ayudó a desarrollar códigos Reed-Solomon). Al igual que los códigos Reed-Solomon, los códigos Reed-Muller utilizan polinomios con muchos términos sumados para codificar mensajes largos.

Los polinomios utilizados en los códigos Reed-Solomon implican una sola variable, x, por lo que la única forma de agregar más términos es usar poderes de mayor x. Esto da como resultado una curva con muchos movimientos que sólo se pueden precisar observando muchos puntos. En cambio, los códigos Reed-Muller utilizan polinomios en los que cada término puede contener múltiples variables multiplicadas entre sí. Más variables significan más formas de combinarlas, lo que a su vez ofrece una manera de aumentar el número de términos polinomiales sin elevar ninguna variable individual a potencias tan altas.

Los códigos Reed-Muller son muy flexibles. Puede codificar mensajes más largos aumentando la potencia más alta que aparece en el polinomio, aumentando el número de variables o ambas cosas. Para hacer que un código Reed-Muller sea corregible localmente, simplemente limite la potencia máxima de cada variable a un pequeño valor constante y maneje mensajes más largos aumentando solo el número de variables.

Para un código de tres consultas corregible localmente específicamente, esa potencia máxima se establece en 2. Luego, en lo que respecta a cada variable individual, el polinomio que codifica el mensaje traza una parábola simple. Para determinar la forma exacta de esa parábola, sólo necesitas examinar la curva en tres puntos. Es más, con muchas variables existen muchas parábolas de este tipo, cualquiera de las cuales puede usarse para corregir errores. Eso es lo que hace que los códigos Reed-Muller sean tan resistentes.

Desafortunadamente, el código Reed-Muller tiene un serio inconveniente: el número de bits necesarios para codificar un mensaje aumenta exponencialmente con el número de variables. Si desea un código altamente local que corrija errores con solo un puñado de consultas, necesitará muchas variables para mensajes largos, y el código Reed-Muller rápidamente se volverá inútil en la práctica.

"El exponencial en este caso es muy malo", dijo Dvir. ¿Pero es inevitable?

¿Corregible o decodificable?

Cuando los científicos informáticos intentaron y no lograron encontrar códigos corregibles localmente más eficientes, comenzaron a sospechar que tales códigos no eran posibles en absoluto. En 2003, dos investigadores demostrado que no hay manera de superar el código Reed-Muller usando sólo dos consultas. Pero eso es lo más lejos que nadie llegó.

"Una vez que llegas a tres, nuestro conocimiento se vuelve muy incompleto", dijo Kothari.

El siguiente avance simplemente complicó aún más las cosas. En dos artículos publicados en 2008 y 2009, los informáticos Sergey Yekhanin y Klim Efremenko mostraron cómo construir códigos de tres consultas que eran más eficientes que los códigos de Reed-Muller, pero estos códigos no eran corregibles localmente. En cambio, tenían una propiedad sutilmente diferente llamada decodificabilidad local.

Para comprender la diferencia, imaginemos nuevamente un proveedor de almacenamiento en la nube que combina los datos de los usuarios en un mensaje largo y los protege mediante un código de corrección de errores. Tanto los códigos corregibles localmente como los códigos decodificables localmente pueden corregir un error en cualquier parte del mensaje original con sólo unas pocas consultas.

Pero cada código de corrección de errores también requiere bits adicionales que no estaban en el mensaje original; es por eso que codificar un mensaje lo hace más largo. Los dos tipos de códigos difieren en cómo tratan estos bits adicionales. Los códigos decodificables localmente no prometen la cantidad de consultas necesarias para corregir errores en estos bits. Pero en un código corregible localmente, un error en cualquiera de los bits adicionales se puede corregir exactamente de la misma manera que un error en cualquier bit del mensaje original.

"Todo lo que se almacena, ya sean los datos originales de los usuarios o la redundancia y la información de verificación, todo esto se puede corregir localmente", dijo Madhu Sudán, científico informático de la Universidad de Harvard.

Aunque diferentes en principio, la corregibilidad local y la decodificabilidad local siempre parecieron intercambiables en la práctica antes de 2008: cada código conocido localmente decodificable también era corregible localmente. El descubrimiento de Yekhanin y Efremenko planteó la posibilidad de una diferencia fundamental entre las dos condiciones. O tal vez fuera posible modificar los códigos de Yekhanin y Efremenko para hacerlos corregibles localmente. Eso pondría las dos condiciones en pie de igualdad una vez más, pero también significaría que los investigadores se habían equivocado acerca de cuán eficientes podrían llegar a ser los códigos de tres consultas corregibles localmente. De cualquier manera, la sabiduría convencional tendría que cambiar.

Lógica de endeudamiento

Kothari y Manohar finalmente resolvieron esa tensión adaptando una técnica de un área diferente de la informática: el estudio de los llamados problemas de satisfacción de restricciones. Tratar de coordinar planes para cenar con un grupo de amigos es una especie de problema de satisfacción de restricciones. Todo el mundo tiene opciones que aceptará y opciones que vetará. Su trabajo es encontrar un plan que satisfaga a todos o, si no existe tal plan, resolverlo lo antes posible.

Existe una asimetría inherente entre esos dos posibles resultados. Puede que no sea fácil encontrar una solución aceptable, pero una vez que la tienes, es fácil convencer a los demás de que funcionará. Pero incluso si sabes que el problema es realmente “insatisfactorio”, puede que no haya un ejemplo que lo demuestre.

En 2021, Kothari y Manohar, junto con Venkatesan Guruswami de la Universidad de California, Berkeley, hicieron un avance importante en el estudio de problemas de satisfacción de restricciones utilizando una nueva técnica teórica para identificar aquellos casos complicados e insatisfactorios. Sospechaban que el nuevo método también sería una herramienta poderosa para resolver otros problemas, y el estudiante graduado de Guruswami, Omar Alrabiah, sugirió que examinaran códigos de tres consultas decodificables localmente.

“Esto fue un clavo con un martillo en la mano, por así decirlo”, dijo Kothari.

Los sorprendentes resultados de Yekhanin y Efremenko habían demostrado que los códigos decodificables localmente de tres consultas podrían ser más eficientes que los códigos de Reed-Muller. Pero, ¿eran sus códigos los mejores posibles o los códigos decodificables localmente con tres consultas podrían volverse aún más eficientes? Kothari, Manohar, Guruswami y Alrabiah pensaron que su nueva técnica podría demostrar los límites de la eficiencia de dichos códigos. Su plan era construir una fórmula lógica que abarcara la estructura de todos los posibles códigos de tres consultas localmente decodificables de un tamaño determinado, y demostrar que era insatisfactoria, demostrando así que tal código no podría existir.

Los cuatro investigadores dieron un primer paso en esa dirección en 2022, estableciendo un nuevo límite sobre la máxima eficiencia de códigos decodificables localmente de tres consultas. El resultado fue mucho más allá de lo que los investigadores habían podido lograr con otras técnicas, pero no descartó todos los códigos más eficientes que los de Yekhanin y Efremenko.

Kothari y Manohar sospecharon que podían llegar más lejos. Pero el progreso se estancó hasta que Manohar anotó un rápido cálculo que indicaba que la técnica podría funcionar incluso mejor para códigos corregibles localmente que para los decodificables localmente.

Unos meses más tarde, después de muchos más comienzos en falso que les hicieron temer haber sido demasiado optimistas, la técnica finalmente cumplió su promesa. Kothari y Manohar demostraron que, como los investigadores habían sospechado, es imposible que un código de tres consultas corregible localmente funcione apreciablemente mejor que los códigos Reed-Muller. Esa escala exponencial es una limitación fundamental. Su resultado fue también una dramática demostración de que la corregibilidad local y la decodificabilidad local, aunque superficialmente similares, en realidad difieren en un nivel fundamental: la última es inequívocamente más fácil de realizar que la primera.

Kothari y Manohar ahora esperan ampliar sus técnicas para estudiar códigos que puedan realizar más de tres consultas, ya que ahora se sabe muy poco sobre ellos. Y el progreso en la teoría de la corrección de errores a menudo tiene implicaciones en otros campos aparentemente no relacionados. En particular, los códigos corregibles localmente aparecen por sorpresa en todas partes, desde el problema de búsquedas en bases de datos privadas en criptografía a pruebas de teoremas en combinatoria. Es demasiado pronto para decir cómo afectará la técnica de Kothari y Manohar a estos diferentes campos, pero los investigadores se sienten optimistas.

"Aquí hay una idea nueva realmente hermosa", dijo Dvir. "Creo que hay mucho potencial".