Investigación realizada por IOG plantea un nuevo protocolo de consenso, probadamente seguro, a fin de reducir al mínimo el desperdicio de energía de las blockchain basadas en proof-of-work (prueba de trabajo)
La reducción al mínimo del coste energético y de la emisión de carbono del protocolo proof of work (PoW) [Prueba de Trabajo] constituye uno de los debates más intensos en el espacio de las criptomonedas. Sustituir el primitivo PoW del protocolo de la cadena más larga de Nakamoto [Bitcoin] por uno de Prueba de Trabajo Útil (PoUW) [proof of useful work] se ha considerado durante mucho tiempo como una solución ideal en muchos aspectos pero, hasta la fecha, el concepto ha carecido de una realización convincentemente segura.
Precisamente hoy [15 ago, 2022], en la principal conferencia internacional de criptología, 
Crypto, Input Output Global, Inc (IOG) presenta Ofelimos, un novedoso protocolo blockchain basado en PoUW cuyo mecanismo de consenso ejecuta simultáneamente un solucionador de problemas de optimización descentralizado. Su mecanismo de consenso utiliza el trabajo para resolver problemas computacionales de interés práctico para mantener la blockchain.
Prueba de trabajo frente a prueba de trabajo útil
[Proof of work (PoW) versus Proof of Useful Work (PoUW)]
Un protocolo blockchain basado en PoW rentabiliza el trabajo realizado por los participantes en el protocolo, denominados mineros. PoW garantiza la seguridad del libro de contabilidad animando a los mineros a competir en la resolución de problemas computacionales para ser elegibles para producir un nuevo bloque. El trabajo de cómputo mantiene la seguridad del protocolo, pero requiere un uso significativo de energía y recursos. En el momento de escribir este artículo, Bitcoin tiene un gasto energético anualizado a la altura de muchos países pequeños y medianos.
Con la Prueba de Trabajo Útil [PoUW] se aborda el problema de la eficiencia energética reutilizando el esfuerzo computacional necesario para mantener la seguridad del protocolo para resolver problemas complejos del mundo real como la optimización de la logística de la empresa o la programación de eventos, por ejemplo.
Uno de los retos de PoUW es resolver el siguiente dilema: si los problemas a resolver son realmente útiles (procedentes del mundo real), el atacante puede dirigir el sistema para plantear instancias de problemas fácilmente superables (o ya resueltos por el atacante). Esto aprovecharía los recursos del atacante para producir más bloques que un participante honesto con la misma cantidad de recursos, y por tanto reduciría la seguridad de la cadena de bloques. Por otro lado, minimizar la capacidad del atacante para aprovechar su producción de bloques puede requerir plantear instancias de problemas aleatorias, lo que haría que los cálculos del sistema fueran inútiles en la práctica.
Ofelimos soluciona este dilema con un análisis formal de seguridad y utilidad.
Perspectiva general de Ofelimos
Los clientes publican los problemas que hay que resolver y las recompensas que hay que pagar a los mineros que tienen éxito. Al igual que en PoW, los mineros trabajan en estos problemas para participar en una lotería que decide la posibilidad de crear bloques.
En el PoW puro, esta lotería suele consistir en realizar repetidamente el hash de un desafío (junto con un contador) contra un valor objetivo determinado. La lotería se gana si el valor del hash está por debajo del objetivo. Tenga en cuenta que en PoW puro, una sola consulta es rápida mientras que la probabilidad de alcanzar el objetivo es muy pequeña.
Como consecuencia de múltiples factores, en PoUW también es aconsejable que una única consulta sea (relativamente) rápida, lo que minimiza la probabilidad de que se publiquen varios bloques de forma simultánea, por ejemplo. En cambio, las instancias del problema del cliente deben ser no triviales de resolver para que la externalización del cómputo sea atractiva. Para el PoUW, es por tanto natural apuntar a clases de computación que sean complejas en su conjunto, pero divisibles en pequeños pasos “uniformes”. Cada paso debería requerir la misma cantidad de trabajo (en expectativa) y corresponder a una única consulta de PoW pura.
La búsqueda local estocástica (SLS) es una clase obvia de tales cálculos. Los algoritmos SLS se aplican a problemas de optimización para los que no se conocen algoritmos deterministas eficientes. En lugar de ello, SLS realiza un paseo aleatorio en el espacio de soluciones tratando de optimizar gradualmente la solución utilizando cierta heurística. Como cada paso de exploración en el paseo aleatorio es una instancia diferente del mismo cálculo, el SLS es un candidato excelente para el PoUW de acuerdo con los requisitos anteriores. Además, el SLS tiene una gran relevancia práctica con aplicaciones en la economía real en áreas como la planificación logística, la programación de eventos, etc.
A continuación resumimos cómo transformar el PoW puro en PoUW en este escenario.
- En el PoW puro, un minero ha de ampliar su cadena con un nuevo bloque, realizando un hashing repetitivo del nuevo bloque contra un objetivo determinado (variando un contador incluido en el bloque). Para empezar, reemplazamos el hashing repetitivo por el cómputo repetido del paso de exploración M del SLS sobre un estado de exploración previo s almacenado en la cadena, donde el bloque determina la semilla aleatoria para el paso de exploración. Consulte la figura 1 (lado derecho): Se amplía un estado de exploración previo s mediante el paso de exploración aleatorio M utilizando la semilla resultante del hashing del bloque junto con el estado s, dando lugar a un nuevo estado de exploración (posiblemente mejor) s’. Se repite este proceso hasta que se cumple una condición aún no especificada ‘?’, lo que permite al minero publicar el bloque. A lo largo de este proceso, el minero mantiene un registro del mejor estado sbest que se ha encontrado durante este proceso repetitivo.
Figura 1: Hashing contra un objetivo T (PoW, izquierda). Repetición del paso de exploración M (PoUW, derecha).
- Ahora fijamos la condición de éxito que falta ‘?’ Con el fin de conseguir buenas propiedades estocásticas no sesgadas por el cálculo concreto, la búsqueda de un bloque se desvincula de la calidad del estado calculado s’, añadiendo, tras el paso de exploración, un ‘post-hash’ al paso de exploración (reutilizando la semilla inicial) -véase la figura 2- y el bloque es elegible para su publicación si este valor hash está por debajo de algún objetivo T3. Esto introduce, además de la mejor solución actual sbest, un nuevo estado sT que debe publicarse con el bloque, el estado que lleva al hash por debajo de T3 - para demostrar la elegibilidad para la publicación del bloque. Obsérvese que sólo sbest sirve como actualización del estado (para ser explorado posteriormente por los mineros) mientras que sT sólo sirve como testigo de la elegibilidad para publicar el bloque.
Figura 2: Aleatorización de la elegibilidad para publicar el bloque
- Tomando en consideración que M es más difícil de calcular que H, y que no todas las instancias de M pueden requerir la misma cantidad de trabajo, el adversario podría moler para obtener semillas que le permitan acelerar su cálculo de M en comparación con un minero honesto, obteniendo así una ventaja en la producción de bloques más rápida y degradando la seguridad del sistema. Contrarrestamos este tipo de trituración exigiendo que el hash inicial esté por debajo de un objetivo T1. Así, antes de ejecutar el paso de exploración M, el minero debe encontrar un valor de hash bajo variando el contador de bloques en la línea del PoW puro. Consulte la figura 3. Concretamente, T1 se elige de forma que el trabajo esperado para encontrar un valor hash por debajo del objetivo T1 cueste al menos tanto como la complejidad temporal del peor caso de calcular M - haciendo que la molienda de una instancia fácil sea tan costosa como calcular una instancia “inconveniente” de M. Una tripleta (Bctr, sbest, sT) que satisfaga las condiciones anteriores constituye, por tanto, un PoUW.
Figura 3: Defensa contra la trituración mediante el pretratamiento contra el objetivo T1
- En contraste con el PoW puro, no podemos plantearnos que los nodos verifiquen los PoUWs repitiendo el cómputo M del minero, ya que esto implicaría una cantidad masiva de cómputo replicado y, por tanto, reduciría drásticamente esa fracción de cómputo verdaderamente útil en el sistema. A fin de impedirlo, al “encontrar” un bloque publicable, el minero debe crear un argumento sucinto no interactivo (SNARG) para demostrar dicho éxito, con la ventaja de que la complejidad de la verificación se vuelve independiente de la complejidad para calcular M. Además, se demuestra el cálculo correcto de la mejor solución sbest. Véase la figura 4.
Figura 4: Minimización de la verificación distribuida añadiendo una prueba no interactiva
- La instancia del SLS se paraleliza para obtener ventajas de la minería concurrente distribuida (por ejemplo, manteniendo múltiples rutas de exploración) ya que, de lo contrario, todos los mineros estarían explorando concurrentemente el mismo estado, introduciendo una gran cantidad de pasos de exploración (esencialmente) redundantes. Conviene señalar que, por razones de seguridad, la producción de bloques en el PoW “Nakamoto” estándar es lenta, y que las actualizaciones de estado están vinculadas a los bloques. En cambio, las actualizaciones de estado deben ser rápidas para evitar que los mineros exploren estados “obsoletos”. Por tanto, introducimos dos tipos de bloques, los bloques de clasificación “difíciles de encontrar” con la misma función que en el consenso Nakamoto, y los bloques de entrada “fáciles de encontrar” que funcionan como transacciones para ser eventualmente referenciadas por los bloques de clasificación. De este modo, la mejor solución de un minero puede difundirse con relativa rapidez, manteniendo así a todos los mineros al día. En concreto, esto se consigue evaluando primero el hash final frente a un T3 objetivo “fácil”. Si está por debajo, se califica como un bloque publicable, pero sólo si el objetivo está por debajo de un objetivo ‘más difícil’ T2, el bloque se califica como un bloque de clasificación ‘relevante para el consenso’ - de lo contrario se define como un bloque de entrada. Véase la figura 5.
Figura 5: Un post-hash por debajo de T2 califica el bloque como bloque de clasificación. Un post-hash entre T2 y T3 califica el bloque como bloque de entrada
Propiedades del protocolo
Hacer un análisis exhaustivo de la seguridad y la utilidad del protocolo está fuera del alcance de este artículo. No obstante, puede ser útil reiterar algunas intuiciones sobre por qué el protocolo es seguro y concluir examinando la eficiencia del mismo.
Seguridad de la cadena de bloques:
- Recolección: el adversario no tiene ninguna ventaja al rectificar instancias de M fáciles de calcular. Esto se consigue adaptando el umbral de precontratación T1 de forma que calcular M en cualquier instancia sea como máximo tan difícil como encontrar una nueva precontratación por debajo de T1 (en expectativa).
- Resistencia contra la ventaja del adversario: La ventaja del adversario para calcular el PoUW más rápido que las partes honestas es limitada. Esto se consigue desvinculando el éxito de los bloques del cálculo real, y realizando un prehash por debajo del objetivo T1. En particular, siguiendo el modelo estándar en [GKL14, PSS16], y asumiendo que el adversario no tiene ninguna ventaja en calcular M más rápido que las partes honestas, el protocolo tolera que un adversario controle cualquier minoría de la potencia de cálculo dedicada a la red - al igual que Bitcoin. Por el contrario, incluso si el adversario fuera capaz de computar M sin coste alguno en cada instancia, el protocolo sigue tolerando que un adversario controle hasta un tercio de todos los recursos computacionales - ya que seguirían operando a “mitad” de coste debido al pretratamiento contra T1.
- Dificultad variable: En los protocolos de consenso PoW/PoUW, la dificultad para encontrar un bloque debe adaptarse continuamente al nivel actual de potencia de cálculo que se dedica al sistema. En Ofelimos esto se consigue fácilmente adaptando el objetivo T2 para el (único) post-hash ejecutado tras el paso de exploración - que califica para la publicación de un bloque de clasificación.
Eficiencia:
- Actualizaciones frecuentes: Esta separación entre los bloques de clasificación y los bloques de entrada garantiza una rápida difusión de las actualizaciones de estado.
- Utilidad: Entendemos por utilidad la proporción del trabajo computacional global que se invierte en el problema del SLS (esto es una simplificación - una definición más cuidadosa, y un análisis, pueden encontrarse en este paper). Las principales fuentes de trabajo “inútil” en el sistema son el pretratamiento repetitivo contra T1, y el cálculo del SNARG. Tenga en cuenta que:
- el pretratamiento sólo se realiza una vez por cada invocación de M y, en comparación con la complejidad de M, puede despreciarse por razones prácticas.
- el SNARG sólo tiene que ser computado con respecto a dos de las muchas invocaciones de M, la que produce sT (que implica el éxito del bloque) y sbest (la mejor solución). La sobrecarga causada por el cómputo de los SNARG puede así minimizarse reduciendo el umbral T3 que determina el éxito del bloque, en una compensación por la lentitud de las actualizaciones de estado.
El grado de utilidad viene dado por las características de M. Si el tiempo de ejecución de M está suficientemente concentrado, la dureza del pre-hash puede establecerse de forma que se acerque a la complejidad del caso medio de M. Según las observaciones anteriores, la utilidad de aproximadamente ½ se consigue cuando el minero pasa aproximadamente la mitad de su tiempo computando M. Numerosos problemas clásicos de SLS parecen estar en esta categoría. En cambio, si M no se comporta bien, la utilidad puede ser cercana a cero. La elección de los algoritmos SLS concretos y sus pasos de exploración M es, por tanto, crucial para conseguir PoUW con una utilidad razonable.
Conclusión
Ofelimos constituye tan solo una primera etapa hacia un PoUW demostrablemente seguro y útil. Si bien el trabajo actual proporciona fácilmente una seguridad demostrable para niveles de corrupción elevados, todavía se necesita más investigación en el lado algorítmico para proporcionar clases adecuadas de problemas de optimización para los que se pueda demostrar una alta utilidad.
El documento de investigación
Agradezco a Matthias Fitzi su aportación y apoyo en la preparación de este artículo.
Traducción al español de “Introducing Ofelimos: a proof-of-useful-work consensus protocol”, escrito por Olga Hryniuk del Departamento de Marketing y Comunicaciones de IOG, el 15 de agosto de 2022.
Notas del traductor
- Corchetes del traductor.
- indica que el enlace apunta a un contenido en idioma inglés.
indica que el enlace apunta a un contenido en idioma español.