Escrito por: Miranda Christ, Joseph Bonneau

Compilación: Deep潮 TechFlow

A medida que la blockchain admite más usuarios y transacciones más frecuentes, la cantidad de información que los validadores almacenan para verificar las transacciones (es decir, el "estado") también está aumentando. Por ejemplo, en Bitcoin, el estado está compuesto por un conjunto de salidas de transacciones no gastadas (UTXO). En Ethereum, el estado está compuesto por el saldo de cada cuenta y el código y almacenamiento de cada contrato inteligente.

A medida que la blockchain crece para soportar una parte sustancial de la población con transacciones verdaderamente diarias, esta carga de almacenamiento se volverá difícil de manejar, dificultando convertirse en validador y amenazando la descentralización. La solución tentadora es recurrir a la criptografía, donde herramientas como los árboles de Merkle y las pruebas de cero conocimiento nos ayudan a lograr cosas que antes eran inimaginables.

Este es precisamente el objetivo de una "blockchain sin estado". Pero a pesar de la extensa investigación realizada sobre ellas, todavía están lejos de ser prácticas. Sin embargo, este retraso en el progreso resulta ser inherente: la brecha entre la construcción y la practicidad nunca podrá cerrarse. Nuestro trabajo reciente muestra que, sin medidas adicionales para gestionar el estado, cualquier solución de blockchain sin estado, no importa cuán inteligente sea, es inviable. Sin embargo, como mostramos al final de este artículo, este resultado de imposibilidad no debería desanimar.

Sin estado

Hoy en día, el estado es grande pero manejable. Por ejemplo, los nodos de Bitcoin almacenan alrededor de 7 GB de datos, mientras que los nodos de Ethereum almacenan alrededor de 650 GB de datos. Sin embargo, la carga de almacenamiento de los nodos completos crece aproximadamente de manera lineal con el rendimiento de la cadena (número de transacciones por segundo o TPS), y el rendimiento actual sigue siendo inaceptable. Según el diseño actual, el estado necesario para soportar transacciones diarias (de decenas de miles a cientos de miles de transacciones por segundo) se volverá difícil de manejar, requiriendo almacenamiento en gigabytes o incluso petabytes.

Esto impulsa la búsqueda de métodos técnicos para reducir significativamente la cantidad de estado requerida por los validadores. Es crucial lograr una blockchain sin estado, lo que requeriría que los validadores almacenaran solo un estado de tamaño constante, sin importar el rendimiento de las transacciones (de hecho, el término es un error: todavía hay estado, pero es lo suficientemente pequeño como para ser práctico bajo cualquier rendimiento futuro, generalmente de tamaño constante). Este requisito de almacenamiento ligero facilitaría la ejecución de nodos validador; en un escenario optimista, todos podrían ejecutar un nodo en sus teléfonos móviles. Dado que aumentar el número de validadores incrementa la seguridad de la cadena, es muy importante reducir la barrera de entrada para los validadores.

A pesar de la extensa investigación sobre las blockchains sin estado (por ejemplo, investigaciones realizadas por Todd, Buterin, Boneh, entre otros, y por Srinivasan y otros), aún están lejos de ser prácticas, y hasta donde sabemos, ninguna ha sido desplegada. El problema fundamental de todas las blockchains sin estado conocidas es que requieren que los usuarios almacenen datos adicionales llamados testigos para ayudar a los validadores a verificar las transacciones que involucran sus cuentas. Por ejemplo, este testigo podría ser una prueba de inclusión de Merkle que muestra que la cuenta y el saldo del usuario están incluidos en el compromiso del estado global. Cuando los usuarios realizan transacciones, presentan este testigo al validador para demostrar que su cuenta tiene suficiente saldo.

A diferencia de las claves privadas que nunca necesitan cambiar, estos testigos cambian con frecuencia, incluso para usuarios con transacciones inactivas, lo que impone una carga poco práctica a los usuarios. De manera similar, imagina si tuvieras que monitorear todas las transacciones de tarjetas de crédito en el mundo y actualizar algunos datos locales en consecuencia para usar tu propia tarjeta de crédito. Para que la blockchain sea práctica, los usuarios deben poder interactuar con la blockchain de forma offline y solo al momento de enviar transacciones. En muchos casos, como en las billeteras de hardware, actualizar los testigos no solo es inconveniente, sino que es imposible.

Esto nos lleva a plantear una pregunta de investigación natural: ¿Podemos construir una blockchain sin estado que no requiera actualizaciones frecuentes de testigos (o solo requiera actualizaciones mínimas)? Para responder a esta pregunta, desarrollamos un marco teórico novedoso (sistema de prueba revocable) que generaliza la blockchain sin estado. Usando este marco, demostramos un resultado de imposibilidad: el compromiso de un estado global conciso y las actualizaciones frecuentes de testigos son inherentemente difíciles de reconciliar. Nuestra técnica de prueba es de teoría de la información, lo que significa que las computadoras del futuro no tendrán la capacidad suficiente para resolver este problema: la brecha entre la construcción de la blockchain sin estado y la practicidad nunca podrá cerrarse.

El contexto que estudiamos

Para ayudar a entender nuestro resultado de imposibilidad, primero describimos un enfoque natural pero ineficiente para construir una blockchain sin estado utilizando árboles de Merkle. Nuestro objetivo es permitir que los validadores determinen si las transacciones enviadas por los usuarios son válidas, es decir, si los usuarios tienen suficiente saldo en sus cuentas para realizar la transacción. En la solución de blockchain sin estado, el validador almacena un estado de tamaño constante. Cuando un usuario realiza una transacción, debe incluir un testigo en la transacción. El validador puede utilizar el estado actual y el par (transacción, testigo) presentado por el usuario para verificar si el usuario tiene suficiente saldo en su cuenta para realizar la transacción.

Primero construimos un árbol de Merkle en el que cada par (ID de cuenta, saldo) (a, b) se incluye como un nodo hoja. El estado de tamaño constante V que almacena el validador es la raíz de este árbol, que actúa como un compromiso de un conjunto de pares de saldo de cuentas. Cada usuario mantiene su testigo como una prueba de inclusión de Merkle. Una prueba de inclusión de Merkle de una hoja (a, b) está compuesta por los nodos compañeros (v1, …, vk) en el camino desde esa hoja hasta la raíz del árbol. Dada una transacción realizada por la cuenta a y el saldo reclamado b, el validador puede verificar si b es efectivamente el saldo de la cuenta a mediante la comprobación de la prueba (v1, …, vk) con su estado actual V. Si es así, el validador ejecuta la transacción y debe actualizar el saldo de la cuenta en consecuencia. Una propiedad conveniente de los árboles de Merkle es que, dada una prueba de inclusión de una hoja, cuando esa hoja cambia, calcular la raíz resultante es fácil. En otras palabras, el validador puede calcular fácilmente un nuevo estado actualizado V' que capture el nuevo saldo de la cuenta a después de ejecutar la transacción.

Este esquema de árbol de Merkle tiene dos desventajas principales. Primero, los testigos de los usuarios son relativamente grandes y crecen con el logaritmo del número total de cuentas en el sistema. Idealmente, deberían ser de tamaño constante, lo que podemos lograr utilizando esquemas como acumuladores RSA.

La segunda desventaja es más difícil de evitar: cada vez que otros usuarios realizan transacciones, la prueba de los pares de saldos de cuentas cambia. Recuerda que la prueba de un nodo hoja está constituida por los nodos compañeros en el camino desde esa hoja hasta la raíz del árbol. Si otros nodos hoja cambian, uno de esos nodos cambiará, lo que plantea un problema práctico. La mayoría de los usuarios de blockchain desean mantener sus monedas en sus billeteras de manera pasiva y solo conectarse cuando desean realizar transacciones. Sin embargo, en esta blockchain sin estado, los usuarios deben monitorear constantemente las transacciones de otros para mantener su información de testigos actualizada. Aunque terceros pueden realizar este monitoreo en nombre de los usuarios, esto se desvía del modelo estándar de blockchain sin estado. De hecho, este es un desafío insuperable para las blockchains sin estado y representa una carga pesada para los usuarios.

Nuestra conclusión: La ausencia de estado es imposible

Este fenómeno no se limita a esta estructura de árbol de Merkle: todos los esquemas de blockchain sin estado conocidos requieren que los usuarios actualicen frecuentemente su información de testigos, lo que hemos demostrado aquí. Más precisamente, mostramos que el número de usuarios que deben actualizar su información de testigos crece aproximadamente de manera lineal con el número total de transacciones realizadas por todos los usuarios.

Esto significa que incluso si el usuario Alice no realiza ninguna transacción, su información de testigos podría necesitar cambiar junto con las transacciones de otros usuarios. Siempre que el estado conciso almacenado por el validador sea demasiado pequeño para capturar el estado completo (es decir, el conjunto de todos los saldos de cuentas), aumentar el tamaño del estado conciso ayuda poco. Hemos graficado la relación que se muestra a continuación, basada en nuestro teorema, así como la cantidad de cambios de información de testigos requeridos diariamente para blockchains de diferentes rendimientos. Estos gráficos muestran el número de cambios de información de testigos que requiere la mejor blockchain sin estado. Aquí, el universo de datos se refiere al número total de cuentas en el modelo de cuentas o al número total de UTXOs en el modelo de UTXO.

El núcleo de nuestra demostración es un argumento de teoría de la información. Un principio central de la teoría de la información, formalizado por Claude Shannon, es que si Alice elige aleatoriamente un objeto de un conjunto de tamaño 2n y desea decirle a Bob qué objeto eligió, debe enviarle al menos n bits. Si existe un esquema de blockchain sin estado en el que los usuarios actualizan poco su información de testigos, Alice podría decirle a Bob qué objeto eligió con menos de n bits, lo cual es imposible, como lo demostró Shannon. Por lo tanto, tal blockchain sin estado no existe.

Para simplificar, aquí describimos una demostración de una afirmación ligeramente más débil: no existe una blockchain sin estado donde los usuarios nunca necesiten actualizar su información de testigos. Lo clave es que Alice usa una solución de blockchain sin estado para codificar sus mensajes y enviarlos a Bob. Inicialmente, tanto Alice como Bob conocen el conjunto completo de pares de saldos de cuentas de todos los n usuarios. Supongamos que cada cuenta tiene al menos una moneda. Alice y Bob también conocen el estado conciso V de la blockchain sin estado y los testigos wi de todos los pares de saldos de cuentas (ai, bi). Además, Alice y Bob acuerdan una relación de mapeo entre los mensajes y el conjunto de cuentas. Alice seleccionará un conjunto de cuentas A que corresponda a su mensaje y luego gastará monedas de esas cuentas. Ella usará la blockchain sin estado para comunicar a Bob el conjunto que eligió, y él podrá entender su mensaje a partir de ese conjunto.

Codificación: Alice gasta una moneda de cada cuenta en A. Usando la solución de blockchain sin estado, Alice calcula el estado actualizado V' y se lo envía a Bob.

Decodificación: Para cada i, Bob verifica si Verify(wi, (ai, bi)) es verdadero. Bob emite el conjunto de cuentas B tal que Verify(wi, (ai, bi)) = falso.

Bob logró emitir el mismo conjunto que eligió Alice: B = A. Primero, se observa que si Alice gasta una moneda de la cuenta ai, el testigo de su saldo anterior no debería ser aceptado: de lo contrario, Alice podría realizar un doble gasto. Por lo tanto, para cada cuenta ai en A, Verify(wi, (ai, bi)) = falso, y Bob incluirá esa cuenta en B. Por otro lado, Bob nunca incluirá cuentas en B de las que Alice no haya gastado monedas, porque esos saldos permanecen inalterados, y (recordemos que estamos probando una afirmación relajada) sus testigos nunca cambiarán. Por lo tanto, B es exactamente igual a A.

Finalmente, resolvemos nuestra contradicción calculando el número de bits que Alice debería enviar a Bob. Ella puede elegir un subconjunto de 2 elevado a n, por lo que, según la ley de Shannon, debería enviar al menos n bits a Bob. Sin embargo, ella solo envía un estado V' de tamaño constante, que es mucho más corto que n bits.

Aunque utilizamos una blockchain sin estado para describir nuestra demostración, Alice y Bob pueden utilizar diversas estructuras de datos autentificadas para llevar a cabo una comunicación eficiente similar, incluyendo acumuladores, compromisos vectoriales y diccionarios autenticados. Utilizamos una nueva abstracción que llamamos sistema de prueba revocable para formalizar este tipo de estructuras de datos.

Impacto de los resultados

Nuestros resultados indican que no puedes "eliminar el estado mediante criptografía", no existe una solución mágica que nos permita construir una blockchain sin estado donde los usuarios nunca tengan que actualizar sus testigos. El estado no ha desaparecido, sino que se ha transferido de los validadores a los usuarios en forma de actualizaciones de testigos frecuentes.

También hay algunas otras soluciones prometedoras que se desvían del modelo de blockchain sin estado estricta. Una relajación natural de este modelo es permitir que un tercero (que no sea ni el usuario ni el validador) sea responsable de almacenar el estado completo. Este tercero, denominado nodo de servicio de prueba, utiliza el estado completo para generar información de testigos actualizada para los usuarios. Los usuarios luego pueden usar esta información de testigos para realizar transacciones, como lo harían en una blockchain sin estado convencional, donde los validadores aún solo almacenan un estado conciso.

Aunque nuestra discusión hasta ahora se ha centrado en blockchains L1, nuestros resultados también tienen implicaciones para sistemas L2 (como servidores Rollup). Los Rollups (ya sean optimistas o ZK) a menudo utilizan un pequeño valor para almacenar un compromiso de un gran estado en L1. Este estado incluye la cuenta de cada usuario en L2. Esperamos que estos usuarios puedan extraer fondos directamente en L1 (sin necesidad de la cooperación de un servidor L2) mediante la publicación de un testigo sobre su saldo de cuenta actual. Esta configuración es también un caso de nuestro modelo de sistema de prueba revocable. De hecho, se podría argumentar que las blockchains sin estado ya se han implementado en la práctica en forma de Rollups L2.

Sin embargo, desafortunadamente, esto significa que nuestro resultado de imposibilidad se aplica directamente. Los testigos de extracción de Rollup de los usuarios deben cambiar con frecuencia, de lo contrario, casi todo el estado L2 debe escribirse en L1. Por lo tanto, los Rollup de hoy en día generalmente suponen la existencia de un comité de disponibilidad de datos (a veces llamado "validium"), similar a los "nodos de servicio de prueba", que ayudan a los usuarios a calcular nueva información de testigos al momento de la extracción. Nuestro resultado indica que la advertencia a los usuarios en la documentación de Ethereum: "sin datos de transacciones, los usuarios no pueden calcular la prueba de Merkle para demostrar la propiedad de los fondos y ejecutar la extracción" siempre será aplicable.