Computación verificable

La computación verificable (o computación verificada o computación verificada ) permite a una computadora delegar el cálculo de alguna función a otros clientes quizás no confiables , mientras mantiene resultados verificables. Los otros clientes evalúan la función y devuelven el resultado con una prueba de que el cálculo de la función se realizó correctamente. La introducción de esta noción surgió como resultado del fenómeno cada vez más común de " subcontratar " la computación a usuarios no confiables en proyectos como SETI@home y también al creciente deseo de permitir que los dispositivos computacionalmente débiles subcontraten tareas computacionales a un servicio computacional más poderoso, como en la computación en la nube . El concepto se remonta al trabajo de Babai et al., ^[1] y se ha estudiado bajo varios términos, incluidos "computación de verificación" (Babai et al.), "computación delegada", ^[2] "computación certificada", ^[3] y computación verificable. El término computación verificable fue formalizado por Rosario Gennaro, Craig Gentry y Bryan Parno, ^[4] y se hace eco del "cómputo certificado" de Micali. ^[3]

El creciente deseo de externalizar tareas computacionales desde un dispositivo computacional relativamente débil (cliente) a un servicio computacional más poderoso (trabajador), y el problema de los trabajadores deshonestos que modifican el software de su cliente para devolver resultados plausibles sin realizar el trabajo real ^[5] motivaron la formalización de la noción de Computación Verificable. ^[4]

La computación verificable no solo se ocupa de obtener el resultado de la función subcontratada en la entrada del cliente y la prueba de su corrección, sino también de que el cliente pueda verificar la prueba con un esfuerzo computacional significativamente menor que si calculara la función desde cero.

Se ha dedicado considerable atención a la verificación del cálculo de funciones realizadas por trabajadores no confiables, incluido el uso de coprocesadores seguros , ^{[6] [7]} módulos de plataforma confiable (TPM), ^[8] pruebas interactivas , ^{[9] [10]} pruebas verificables probabilísticamente , ^{[11] [12]} argumentos eficientes, ^{[13] [14]} y las pruebas CS de Micali. ^[15] Estas verificaciones son interactivas, lo que requiere que el cliente interactúe con el trabajador para verificar la prueba de corrección, ^{[13] [14]} o son protocolos no interactivos que se pueden probar en el modelo de oráculo aleatorio . ^[15]

El cálculo verificado más grande ( SETI@home ) utiliza la verificación por replicación.

El proceso de verificación de SETI@home involucra una máquina cliente y muchas máquinas de trabajo. La máquina cliente envía unidades de trabajo idénticas a varias computadoras (al menos 2).

Cuando no se obtienen suficientes resultados en un tiempo razonable (debido a que las máquinas se apagan accidentalmente, fallas de comunicación, etc.) o los resultados no concuerdan (debido a errores de cálculo, engaños al enviar datos falsos sin hacer realmente el trabajo, etc.), la máquina cliente envía más unidades de trabajo idénticas a otras máquinas de trabajo. Una vez que un quórum mínimo (a menudo 2) de los resultados concuerda, el cliente asume que esos resultados (y otros resultados idénticos para esa unidad de trabajo) son correctos. El cliente otorga crédito a todas las máquinas que devolvieron los resultados correctos.

Gennaro et al. ^[4] definieron el concepto de esquema de cálculo verificable como un protocolo entre dos partes en tiempo polinomial para colaborar en el cálculo de una función F: {0,1} ⁿ → {0,1} ^m . Este esquema consta de tres fases principales:

1. Preprocesamiento . Esta etapa la realiza el cliente una sola vez para calcular cierta información auxiliar asociada a F. Parte de esta información es pública para ser compartida con el trabajador mientras que el resto es privada y se conserva con el cliente.
2. Preparación de la entrada . En esta etapa, el cliente calcula cierta información auxiliar sobre la entrada de la función. Parte de esta información es pública, mientras que el resto es privado y se conserva en poder del cliente. La información pública se envía al trabajador para calcular F sobre los datos de entrada.
3. Cálculo y verificación de la salida . En esta etapa, el trabajador utiliza la información pública asociada a la función F y la entrada, que se calculan en las dos fases anteriores, para calcular una salida codificada de la función F sobre la entrada proporcionada. Este resultado se devuelve luego al cliente para verificar su exactitud calculando el valor real de la salida mediante la decodificación del resultado devuelto por el trabajador utilizando la información privada calculada en las fases anteriores.

La noción definida de esquema de cálculo verificable minimiza la interacción entre el cliente y el trabajador en exactamente dos mensajes, donde se envía un solo mensaje de cada parte a la otra parte durante las diferentes fases del protocolo. ^[4]

Gennaro et al. ^[4] definieron un esquema de cálculo verificable para cualquier función F utilizando el circuito confuso de Yao ^{[16] [17]} combinado con un sistema de cifrado completamente homomórfico .

Este esquema de cálculo verificable VC se define de la siguiente manera: ^[4]

VC = (KeyGen, ProbGen, Compute, Verify) consta de cuatro algoritmos como se indica a continuación:

1. KeyGen(F, λ) → (PK, SK) : el algoritmo de generación de claves aleatorias genera dos claves, pública y privada, en función del parámetro de seguridad λ. La clave pública codifica la función de destino F y se envía al trabajador para calcular F. Por otro lado, el cliente mantiene privada la clave secreta .
2. ProbGen(SK, x) → (σx, τx) : el algoritmo de generación de problemas codifica la entrada de función x en dos valores, público y privado, utilizando la clave secreta SK. El valor público σx se le proporciona al trabajador para que calcule F(x), mientras que el cliente mantiene privado el valor secreto τx.
3. Compute(PK, σx) → σy : el trabajador calcula un valor codificado σy de la salida de la función y = F(x) utilizando la clave pública PK del cliente y la entrada codificada σx.
4. Verificar _SK (τx, σy) → y ∪ ⊥ : El algoritmo de verificación convierte la salida codificada del trabajador σy en la salida real de la función F utilizando tanto la clave secreta SK como la “decodificación” secreta τx. Genera y = F(x) si σy representa una salida válida de F en x, o genera ⊥ en caso contrario.

El protocolo del esquema de cálculos verificables definido por Gennaro et al. ^[4] funciona de la siguiente manera:

La función F debe representarse como un circuito booleano en el que se aplicaría el algoritmo de generación de claves . El algoritmo de generación de claves ejecuta el procedimiento de codificación de Yao sobre este circuito booleano para calcular las claves pública y secreta. La clave pública (PK) está compuesta por todos los textos cifrados que representan el circuito codificado, y la clave secreta (SK) está compuesta por todas las etiquetas de cable aleatorias. La clave secreta generada se utiliza luego en el algoritmo de generación de problemas. Este algoritmo primero genera un nuevo par de claves pública y secreta para el esquema de cifrado homomórfico , y luego utiliza estas claves con el esquema homomórfico para cifrar los cables de entrada correctos, representados como la clave secreta del circuito codificado. Los textos cifrados producidos representan la codificación pública de la entrada (σx) que se le da al trabajador, mientras que la clave secreta (τx) se mantiene privada por el cliente. Después de eso, el trabajador aplica los pasos de cálculo del protocolo de Yao sobre los textos cifrados generados por el algoritmo de generación de problemas. Esto se hace descifrando recursivamente los textos cifrados de la puerta hasta llegar a los valores finales del cable de salida (σy). Las propiedades homomórficas del esquema de cifrado permiten al trabajador obtener un cifrado del cable de salida correcto. Finalmente, el trabajador devuelve los textos cifrados de la salida al cliente, quien los descifra para calcular la salida real y = F(x) o ⊥.

La definición del esquema computacional verificable establece que el esquema debe ser correcto y seguro. La corrección del esquema se logra si el algoritmo de generación de problemas produce valores que permiten a un trabajador honesto calcular valores de salida codificados que se verificarán correctamente y corresponderán a la evaluación de F en esas entradas. Por otro lado, un esquema computacional verificable es seguro si un trabajador malintencionado no puede convencer al algoritmo de verificación de que acepte una salida incorrecta para una función F y una entrada x dadas.

Aunque se ha demostrado que la computación verificable es posible en teoría (utilizando cifrado totalmente homomórfico o mediante pruebas probabilísticamente comprobables ), la mayoría de las construcciones conocidas son muy caras en la práctica. Recientemente, algunos investigadores han buscado hacer que la computación verificable sea práctica. Uno de esos esfuerzos es el trabajo de los investigadores de UT Austin . ^[18] Los autores comienzan con un sistema de argumentos basado en pruebas probabilísticamente comprobables y reducen sus costos en un factor de 10 ²⁰ . También implementaron sus técnicas en el sistema Pepper. Los autores señalan que "Nuestra conclusión hasta ahora es que, como herramienta para construir sistemas seguros, los PCP y los sistemas de argumentos no son una causa perdida".

Se ha examinado el área en su conjunto, que ahora incluye una serie de implementaciones realizadas por diferentes grupos. ^[19]

En la década de 2010, las técnicas de computación verificables han experimentado un aumento de aplicaciones prácticas en la tecnología blockchain. ^[20]