Una demostración de pruebas de conocimiento cero (ZKP) aplicada a la coloración de grafos explica cómo un demostrador puede convencer a un verificador de que posee una solución válida sin revelar cuál es. El artículo parte del ejemplo canónico del 3-coloreado: dado un grafo compartido, el demostrador coloca los colores de cada vértice en "cajas cerradas" mediante funciones hash, añadiendo un nonce aleatorio a cada nodo para que dos vértices con el mismo color produzcan hashes distintos. Después de aplicar una permutación aleatoria al coloreado para ocultar la estructura, envía las cajas al verificador, que elige al azar una arista y solicita las llaves de sus dos extremos. Si los colores revelados son distintos, la iteración se repite; tras m² rondas independentes, si todas pasan, el verificador acepta. El texto, escrito en tono divulgativo y con código en Python que ronda las 30 líneas, aclara que encontrar un 3-coloreado válido es un problema NP-completo y por tanto costoso, mientras que verificarlo es lineal en el número de aristas. Los autores recomiendan sustituir el hash y el generador aleatorio de la biblioteca estándar por primitivas criptográficas reales (hashlib.sha256, secrets, hmac) si se quisiera llevar el esquema a producción. El texto aclara desde el inicio que no trata sobre criptomonedas y se apoya en el artículo fundacional de Goldreich, Micali y Wigderson para reproducir el protocolo interactivo paso a paso.
Noticias agregadas con IA